楼主:
Rushia (みけねこ的鼻屎)
2024-12-08 16:21:08https://leetcode.com/problems/two-best-non-overlapping-events
2054. Two Best Non-Overlapping Events
给你一个阵列表示活动 events[i] = [startTimei, endTimei, valuei],你最多
可以参加两个活动,活动持续期间不可参加其他活动,求出最多可以获得的value。
思路:
1.先把阵列按照活动结束时间排序。
2.每次参加活动i的时候就往前去找一个活动 j 满足
events[j].endtime < events[i].startTime
因为有单调性所以可以用二分搜索。
3.前面的活动要用一个阵列保存最大的value让二分搜索保持单调性:
[1,2,3,4] [1,2] [1,2,3,4,5] => [1,2,3,4] [4,4] [4,4,4,4,5]
所以我们只要找满足条件的最右活动即可
Java code: