Leetcode 1353. Maximum Number of Events That Can Be Attended

Problem Explanation

The problem is about maximizing the number of events that could be attended considering you can only attend one event at a time. A given list of events contains an array of two elements specifying the start and end of the event. You can attend an event at any day between the start and the end, inclusive.

The goal is to determine the maximum possible number of events which can be attended. To do this, it's more advantageous to opt for events that will end earlier. This is because, events which lasts longer, by nature, provide more flexibility and time to attend them. Therefore, the solution works by sorting the events in an increasing order of their starting times.

Once that's done, it walks through the events. For each day, it adds all events that start that day to a priority queue - a data structure that always allows access to the smallest element - while the priority queue is ordered by the end of events. This is in line with the goal to attend events which end sooner. For each day, if it is possible to attend an event (there are events in the queue), the one that ends earliest is attended and removed from the queue (since we can't go to the same event again).

Let's understand this with an example: Raising by as ascending order of the start times.

1     [ [1, 2], [2, 3], [3, 4], [1, 2]
2     

Sorting as a priority (starting time first and then ascending order of ending times).

1     [ [1, 2], [1, 2], [2, 3], [3, 4]
2     

We can attend the first event on day 1, the second event on day 2, the third event on day 3, and the last event on day 4. This makes the maximum possible event attendance to 4 events.

Python Solution

1
2python
3import heapq
4class Solution:
5    def maxEvents(self, events: List[List[int]]) -> int:
6        events.sort(reverse=True)
7        h = []
8        res = d = 0
9        while events or h:
10            if not h:  # no open events, jump to the next start
11                d = events[-1][0]
12            while events and events[-1][0] <= d: # push all events available to attend today into the heap
13                heapq.heappush(h, events.pop()[1])
14            heapq.heappop(h) # attend the event that closes early
15            res += 1
16            d += 1
17            while h and h[0] < d: # remove events that are already closed
18                heapq.heappop(h)
19        return res

Java Solution

1
2java
3class Solution {
4    public int maxEvents(int[][] events) {
5        Arrays.sort(events, (a, b) -> a[0] - b[0]);
6        PriorityQueue<Integer> pq = new PriorityQueue<>();
7        int i = 0, res = 0, n = events.length;
8        for (int d = 1; d <= 100000; d++) {
9            while (i < n && events[i][0] == d)
10                pq.add(events[i++][1]);
11            while (!pq.isEmpty() && pq.peek() < d)
12                pq.poll();
13            if (!pq.isEmpty()) {
14                pq.poll();
15                ++res;
16            }
17        }
18        return res;
19    }
20}

JavaScript Solution

1
2javascript
3/**
4 * @param {number[][]} events
5 * @return {number}
6 */
7var maxEvents = function(events) {
8    events.sort((a, b) => a[0] - b[0]);
9    let pq = new PriorityQueue((a, b) => a > b);
10    let i = 0, res = 0, n = events.length;
11    for (let d = 1; d <= 100000; d++) {
12        while (i < n && events[i][0] === d)
13            pq.push(events[i++][1]);
14        while (!pq.isEmpty() && pq.peek() < d)
15            pq.pop();
16        if (!pq.isEmpty()) {
17            pq.pop();
18            ++res;
19        }
20    }
21    return res;
22};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maxEvents(vector<vector<int>>& events) {
6        sort(events.begin(), events.end());
7        priority_queue<int, vector<int>, greater<int>> pq;
8        int i = 0, res = 0;
9        for(int d=1; d<=100000; d++){
10            while(i < events.size() && events[i][0] == d)
11                pq.push(events[i++][1]);
12            while(!pq.empty() && pq.top() < d)
13                pq.pop();
14            if(!pq.empty()){
15                pq.pop();
16                ++res;
17            }   
18        }
19        return res;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxEvents(int[][] events) {
5        Array.Sort(events, (a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
6        int res = 0, n = events.Length, i = 0, d = 0;
7        SortedSet<int> set = new SortedSet<int>();
8        
9        while (i < n || set.Count > 0 ) {
10            if(set.Count == 0) {
11                d = events[i][0];
12            }
13            while ( i < n && events[i][0] <= d) {
14                set.Add(events[i++][1]);
15            }
16            set.Remove(set.Min);
17            res++; d++;
18            while (set.Count > 0 && set.Min < d) {
19                set.Remove(set.Min);
20            }
21        }
22        return res;
23    }
24}

These solutions make use of a priority queue approach. Each algorithm follows the same basic steps:

1. Sorting the events array in ascending order based on their start times.
2. Initializing a priority queue (in Python and C++, the priority queue always pops the smallest element first. In Java and C# solutions, elements are sorted based on their ending times (so, the event that ends earlier will always be on the top of the heap).
3. Walking through each day and checking events that can be attended on that day. Push these events into the priority queue.
4. Attending an event on each day if possible (this means if there are events in the heap). Remove the attended events from the priority queue because we can't attend the same events again.
5. Incrementing a counter variable 'res' each time an event is attended.
6. Incrementing the day after attending an event.
7. At the end of each day, remove all events from the priority queue that have already ended (that means if their end day is smaller than the current day).
8. Finally, when we have scanned through all the days, return the result 'res' i.e., the maximum number of events attended.

Correctness and efficiency: The time complexity of these solutions is O(n log n), where n is the number of events. This is due to the sorting of events and the use of a priority queue. The space complexity is O(n), the maximum size of the priority queue.

These solutions are efficient and correct because they ensure that the event with the earliest end time is always attended first whenever multiple events are available on the same day, maximizing the number of events that can be attended.