LC-2054 Medium LeetCode

2054. Two Best Non-Overlapping Events

Array Binary Search Dynamic Programming Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 61% Topics: Array, Binary Search, Dynamic Programming, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import heapq


class Solution(object):
    def maxTwoEvents(self, events):
        """
        :type events: List[List[int]]
        :rtype: int
        """
        events.sort()
        result = best = 0
        min_heap = []
        for left, right, v in events:
            heapq.heappush(min_heap, (right, v))
            while min_heap and min_heap[0][0] < left:
                best = max(best, heapq.heappop(min_heap)[1])
            result = max(result, best+v)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT