Other Interval Greedy¶
Table of Contents¶
- 1288. Remove Covered Intervals (Medium)
- 2054. Two Best Non-Overlapping Events (Medium)
- 1705. Maximum Number of Eaten Apples (Medium)
- 1353. Maximum Number of Events That Can Be Attended (Medium)
- 2589. Minimum Time to Complete All Tasks (Hard)
1288. Remove Covered Intervals¶
2054. Two Best Non-Overlapping Events¶
from bisect import bisect_left
from typing import List
class maxTwoEvents:
@staticmethod
def binary_search(events: List[List[int]]) -> int:
events.sort(key=lambda x: x[1])
stack = [(0, 0)]
res = 0
for start, end, val in events:
i = bisect_left(stack, (start,)) - 1
res = max(res, stack[i][1] + val)
if val > stack[-1][1]:
stack.append((end, val))
return res
if __name__ == "__main__":
events = [[1, 3, 2], [4, 5, 2], [2, 4, 3]]
assert maxTwoEvents.binary_search(events) == 4