Back to Leetcode

Readme

Greedy/2054.Two-Best-Non-Overlapping-Events/Readme.md

latest1.2 KB
Original Source

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数组。