MediumNo. 2054
Two Best Non-Overlapping Events — LeetCode 2054 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Binary Search, Dynamic Programming, Sorting, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei.
Example
- Input
- events = [[1,3,2],[4,5,2],[2,4,3]]
- Output
- 4
- Explanation
- Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.
Python solution
class Solution:
def maxTwoEvents(self, events: List[List[int]]) -> int:
events.sort()
n = len(events)
f = [events[-1][2]] * n
for i in range(n - 2, -1, -1):
f[i] = max(f[i + 1], events[i][2])
ans = 0
for _, e, v in events:
idx = bisect_right(events, e, key=lambda x: x[0])
if idx < n:
v += f[idx]
ans = max(ans, v)
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2054. Two Best Non-Overlapping Events is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0354 | Russian Doll Envelopes | Hard |
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 1187 | Make Array Strictly Increasing | Hard |
| 1235 | Maximum Profit in Job Scheduling | Hard |
| 1268 | Search Suggestions System | Medium |
| 1337 | The K Weakest Rows in a Matrix | Easy |
Frequently asked questions
- How hard is LeetCode 2054. Two Best Non-Overlapping Events?
LeetCode 2054. Two Best Non-Overlapping Events is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2054. Two Best Non-Overlapping Events?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 2054. Two Best Non-Overlapping Events?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2054. Two Best Non-Overlapping Events cover?
LeetCode 2054. Two Best Non-Overlapping Events is tagged Array, Binary Search, Dynamic Programming, Sorting and Heap (Priority Queue) on LeetCode.