That *feels* like throwing information away, but if so that would to recapture the simplicity, and the deadlines have obviously been abstracted into the start times.
My reasoning was to guess to try to work out what S would be from scratch, and reason that you must be able to consider A and B as two separate blocks of time, each of which can be slid about as a unit. But block B must start no later than SB, and you know examining the internals can't help, as all block A must be finished by then, and any block C is less urgent, so it's at least as good to do all B as fast as you can first. So the only keys for S are (a) must start A by SA and (b) must start B by SB, ie. finish A by SB.
And a little munging makes me think that's equivalent to what you wrote.
S = min(SA, EDA-LA) S = min(SA, min(DA,SB)-LA) S = min(SA, min(DA-LA, SB-LA) ) S = min(SA, DA-LA, SB-LA)
But SA<=DA-LA, so
S = min(SA, SB-lA)
I had a different (wrong) simplification earlier which involved two scalars and one "you shipment of fail has arrived" bit, with successive logical ANDs, which was funny but didn't work. (Of course, if your log(N) is large, you may be able to escape early if any S is less than now if you like. But I don't know if that's ever worth it.)
Yes, I agree; I think that does work. It isn't actually throwing information away: since the tree is sorted by deadline, you can always retrieve D for a sublist of your choice by simply finding the last element in the sublist and looking up its deadline. It is slightly surprising to me that you don't directly need those deadlines when computing S, but it does appear to be true.
It is slightly surprising to me that you don't directly need those deadlines when computing S
Exactly.
Although come to think of it, a thought experiment makes it seem plausible that everything is abstracted into S (which is what you *really* want to know, at least for this application, you just can't believe the deadlines aren't important). Imagine A as a block of time allocated from SA with all the tasks running successively in order of deadline. In terms of combining A with other tasks it's just like one task with SA and LA. Does it make a difference if any of the deadlines are moved? If it's a tight deadline (ie. if you start at SA then the task is done exactly by the deadline) then moving it forward is reflected in SA moving forward. If it's the only tight deadline then moving it back is reflected in SA moving back. If not, then it doesn't make any difference to SA, but doesn't make any difference to S either, since you might as well do all the tasks as quickly as you can regardless if any of them have slack or not.
Imagine A as a block of time allocated from SA with all the tasks running successively in order of deadline. In terms of combining A with other tasks it's just like one task with SA and LA.
Ah yes, I think I believe that too. Nice reanalysis!
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
L = LA+LB
S = min(SA,SB-LA)
That *feels* like throwing information away, but if so that would to recapture the simplicity, and the deadlines have obviously been abstracted into the start times.
My reasoning was to guess to try to work out what S would be from scratch, and reason that you must be able to consider A and B as two separate blocks of time, each of which can be slid about as a unit. But block B must start no later than SB, and you know examining the internals can't help, as all block A must be finished by then, and any block C is less urgent, so it's at least as good to do all B as fast as you can first. So the only keys for S are (a) must start A by SA and (b) must start B by SB, ie. finish A by SB.
And a little munging makes me think that's equivalent to what you wrote.
S = min(SA, EDA-LA)
S = min(SA, min(DA,SB)-LA)
S = min(SA, min(DA-LA, SB-LA) )
S = min(SA, DA-LA, SB-LA)
But SA<=DA-LA, so
S = min(SA, SB-lA)
I had a different (wrong) simplification earlier which involved two scalars and one "you shipment of fail has arrived" bit, with successive logical ANDs, which was funny but didn't work. (Of course, if your log(N) is large, you may be able to escape early if any S is less than now if you like. But I don't know if that's ever worth it.)
S = min(SA,SB-LA)
Yes, I agree; I think that does work. It isn't actually throwing information away: since the tree is sorted by deadline, you can always retrieve D for a sublist of your choice by simply finding the last element in the sublist and looking up its deadline. It is slightly surprising to me that you don't directly need those deadlines when computing S, but it does appear to be true.
Exactly.
Although come to think of it, a thought experiment makes it seem plausible that everything is abstracted into S (which is what you *really* want to know, at least for this application, you just can't believe the deadlines aren't important). Imagine A as a block of time allocated from SA with all the tasks running successively in order of deadline. In terms of combining A with other tasks it's just like one task with SA and LA. Does it make a difference if any of the deadlines are moved? If it's a tight deadline (ie. if you start at SA then the task is done exactly by the deadline) then moving it forward is reflected in SA moving forward. If it's the only tight deadline then moving it back is reflected in SA moving back. If not, then it doesn't make any difference to SA, but doesn't make any difference to S either, since you might as well do all the tasks as quickly as you can regardless if any of them have slack or not.
Ah yes, I think I believe that too. Nice reanalysis!