aboutsummaryrefslogtreecommitdiff
path: root/max_num_events_attended.py
blob: 1aaf5918d4235fe677b5423723c8c3f74fd13d9e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 1353. Maximum Number of Events That Can Be Attended
import heapq

"""
you are given an array of 'events' where 'events[i] = [startday_i,
endday_i]'. every event 'i' starts at 'startday_i' and ends at 'endday_i'.
you can attend an event 'i' at any day 'd' where 'starttime_i <= d <=
endtime_i'. you can only attend one event at any time 'd'. return the maximum
number of events you can attend.
"""


class Solution(object):
    def maxEvents(self, events):
        """
        :type events: List[List[int]]
        :rtype: int
        """
        events.sort(reverse=True)
        heap, ans, d = [], 0, 0
        while events or heap:
            if not heap:
                d = events[-1][0]
                while events and events[-1][0] <= d:
                    heapq.heappush(heap, events.pop()[1])
                heapq.heappop(heap)
                ans += 1
                d += 1
                while heap and heap[0] < d:
                    heapq.heappop(heap)
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxEvents(events=[[1, 2], [2, 3], [3, 4]]))
    print(obj.maxEvents(events=[[1, 2], [2, 3], [3, 4], [1, 2]]))