Maximum Number Of Events That Can Be Attended - Leetcode Solution

Problem Statement:

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

You can attend an event i at any day d where startTime_i <= d <= endTime_i. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Approach:

This problem can be solved using a greedy approach. Firstly, we will sort the events in increasing order of their end time. This is because if two events have the same start time, we should always choose the one with the earlier end time.

Next, we will maintain a heap of all events that we can attend. The heap will store the events in increasing order of their start time. We will attend events in increasing order of their end time, and for each event, we will attend the event that ends earliest and is still available.

We will keep attending events until we can't attend any more events. At this point, we will have attended the maximum number of events.

Solution:

Here is the Python code for the solution:

import heapq

class Solution: def maxEvents(self, events: List[List[int]]) -> int: events.sort(key=lambda x: x[1]) heap = [] max_events = 0 day = 1 i = 0

    while heap or i < len(events):
        if not heap:
            day = events[i][0]
            
        while i < len(events) and events[i][0] <= day:
            heapq.heappush(heap, events[i][1])
            i += 1
            
        heapq.heappop(heap)
        max_events += 1
        day += 1
        
        while heap and heap[0] < day:
            heapq.heappop(heap)
            
    return max_events

Time Complexity:

The time complexity of this solution is O(nlog(n)) where n is the number of events. This is because we are sorting the events and using a heap. Sorting takes O(nlog(n)) time and heap operations take O(log(n)) time.

Space Complexity:

The space complexity of this solution is O(n) where n is the number of events. We are using a heap to store the events. The heap can have at most n elements.

1