Readme

2054.Two-Best-Non-Overlapping-Events

本题就是1235. Maximum Profit in Job Scheduling的简化版。在1235中，要求所有non-overlapping的区间的最大权重和。本题中，只需要求两个non-overlapping的区间的最大权重和。

思路差不多。将所有的区间按照endTime排序。我们考察第i个区间[a,b,v]的时候，需要考虑在a时刻之前的那些完整区间里，我们可以收获的“单个区间”的最大收益。为了方便的得到这个数据，我们设计dp数组，里面放入一系列的{time, value}，表示截止到time为止的完整区间里最大的一个value值。于是我们可以利用二分，在dp里找到最后一个小于等于a的时间戳，它所对应value值加上第i个区间本身的v，就是一对可行的解。依次类推，每处理一个区间，我们都利用这个方法找它之前的最大值与之配对。由此我们做到了所有可能配对不重不漏的枚举。

注意，处理完第i个区间后，我们需要将第i个区间的信息也加入dp数组。因为随着时间的推移，dp必然是递增的。所以当我们考虑所有前i个区间的最大值时，必然就是在dp的最后一个值与v之间取较大值vv。然后将{b,v}加入dp数组。