What is the time complexity of LeetCode 1353. Maximum Number of Events That Can Be Attended?

The Python solution on this page runs in O(M \times \log n).

What is the space complexity of LeetCode 1353. Maximum Number of Events That Can Be Attended?

The Python solution on this page uses O(n), where M is the maximum end time and n is the number of events auxiliary space.

Maximum Number of Events That Can Be Attended — LeetCode 1353 Python Solution

MediumGreedyArraySortingHeap (Priority Queue)

Problem: #1353
Pattern: Heap / Priority Queue
Reading time: 3 min
Source: leetcode.com

The problem

You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

Example

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.

Python solution

Python

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        g = defaultdict(list)
        l, r = inf, 0
        for s, e in events:
            g[s].append(e)
            l = min(l, s)
            r = max(r, e)
        pq = []
        ans = 0
        for s in range(l, r + 1):
            while pq and pq[0] < s:
                heappop(pq)
            for e in g[s]:
                heappush(pq, e)
            if pq:
                heappop(pq)
                ans += 1
        return ans

Complexity

Measure	Complexity
Time	O(M \times \log n)
Space	O(n), where M is the maximum end time and n is the number of events auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1353. Maximum Number of Events That Can Be Attended 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.

Frequently asked questions

How hard is LeetCode 1353. Maximum Number of Events That Can Be Attended?: LeetCode 1353. Maximum Number of Events That Can Be Attended is rated Medium on LeetCode.
What is the time complexity of LeetCode 1353. Maximum Number of Events That Can Be Attended?: The Python solution on this page runs in O(M \times \log n).
What is the space complexity of LeetCode 1353. Maximum Number of Events That Can Be Attended?: The Python solution on this page uses O(n), where M is the maximum end time and n is the number of events auxiliary space.
What topics does LeetCode 1353. Maximum Number of Events That Can Be Attended cover?: LeetCode 1353. Maximum Number of Events That Can Be Attended is tagged Greedy, Array, Sorting and Heap (Priority Queue) on LeetCode.