Maximum Number Of Events That Can Be Attended Ii - Leetcode Solution

Problem Statement:

You are given an array of events where events[i] = [starti, endi, ti] and represents an ith event where starti is the start time, endi is the end time, and ti is the index of the hotel where the event takes place. You can attend an event if and only if you can travel to the hotel hosting that event before the event ends.

Once you arrive at the hotel, you must stay for the entire event duration and cannot leave and come back.

You can visit multiple hotels before the same event as long as you do not attend the same event in two different hotels.

Return the maximum number of events you can attend.

Solution Approach:

The solution to this problem can be efficiently solved by taking following steps.

1. Sort the events with respect to end time in increasing order - to attend maximum events possible by attending events that take less time, and finishing the earliest.

2. For each event, take the earliest possible hotel to reach, which means travel time+time to reach hotel before event end should be minimum. For this use min-heap data structure using python's inbuilt heap queue data structure.

3. If there are no hotels to reach on or before event ends, skip to the next event.

4. If the hotel has been already visited, skip this hotel, as we cannot attend the same event in 2 hotels.

Time Complexity:

Sorting: O(nlogn)

Heap addition and deletion: O(nlogn)

Overall time complexity: O(nlogn)

Space Complexity:

O(n) (heap) and O(n) (events) hence total O(n) space.

Python code snippet:

class Solution: def maxEvents(self, events: List[List[int]]) -> int: event_day = [(a, b) for a, b, c in events] # Create extra array of only the start and end times event_day.sort(reverse = True) # Sort by the end time ans = d = 0 # Initialise number of events attended as 0 and current day as 0 while event_day: if not ans: d = event_day[-1][1] # If the day is 0, update to the last day a, b = event_day.pop() # current event considered is the latest scheduled event if d < a: # If current day is less than earliest starting day d = a # Update the earliest day (start event day, at earliest notice) while events and events[-1][0] <= d: # Add hotels available before event start heapq.heappush(day_hotel, events.pop()[1]) if day_hotel: ans += 1 heapq.heappop(day_hotel) d += 1 return ans # Return the answer

1