Maximum Number of Events That Can Be Attended

Problem Id: 1353 Difficulty: Medium Tag: Greedy Tag: Sort Tag: Segment Tree


Intuition

This problem could be simply solved for Greedy. Each time, we choose a new event with the smallest start day. If there are multiple event with this start day, we choose the one with the smallest end day.

Solution


import heapq


class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        heap = []
        for event in events:
            heapq.heappush(heap, event)

        current = 0
        count = 0
        while heap:
            event = heapq.heappop(heap)
            if current >= event[1]:
                continue
            elif event[0] < current + 1:
                event[0] = current + 1
                heapq.heappush(heap, event)
            else:
                current = event[0]
                count += 1
        return count