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.
no subject
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.