LC-1353 Medium LeetCode

1353. Maximum Number of Events That Can Be Attended

Array Greedy Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 33% Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(r + nlogn), r is the max end day of events
# Space: O(n)

import heapq


class Solution(object):
    def maxEvents(self, events):
        """
        :type events: List[List[int]]
        :rtype: int
        """
        events.sort(reverse=True)
        min_heap = []
        result = 0
        for d in xrange(1, max(events, key=lambda x:x[1])[1]+1):
            while events and events[-1][0] == d:
                heapq.heappush(min_heap, events.pop()[1])
            while min_heap and min_heap[0] == d-1:
                heapq.heappop(min_heap)
            if not min_heap:
                continue
            heapq.heappop(min_heap)
            result += 1       
        return result

Solution from kamyu104/LeetCode-Solutions · MIT