We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Events That Can Be Attended

Number: 1478

Difficulty: Medium

Paid? No

Companies: Oracle, Google, PayPal, Snowflake, Amazon, Meta, Uber, Apple, Visa

Problem Description

Given an array of events where each event is defined by a start day and an end day, determine the maximum number of events you can attend with the constraint that you can attend at most one event per day. An event can be attended on any day within its start and end period (inclusive).

Key Insights

  • Sort events by their start day.
  • Use a min-heap (priority queue) to dynamically store events that have started but not yet ended.
  • On each day, add all events starting on that day to the heap.
  • Remove events from the heap that have already ended.
  • Always attend the event that ends the earliest (pop from the heap) to free up future days.
  • Iteratively move through each day until all events are processed.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

The algorithm starts by sorting the events by their start day. Then, using a min-heap, it processes each day from the earliest start day up to the latest possible day among the events. For each day, it adds all events that begin on that day into the min-heap. The heap is used to keep track of the current events by their end days. Events that have ended before the current day are removed from the heap. On each day, if there is any event in the heap, the one with the smallest end day (which gives the best chance for future days) is attended and removed from the heap. This greedy strategy maximizes the total number of events attended.

Code Solutions

import heapq

def maxEvents(events):
    # Sort events by start day
    events.sort(key=lambda x: x[0])
    # Initialize a min-heap and index for events
    min_heap = []
    i = 0
    total_events = 0
    n = len(events)
    # Determine the last possible day to check (max end day among events)
    last_day = max(event[1] for event in events)
    
    # Iterate over each day
    for day in range(1, last_day + 1):
        # Add events starting on the current day to the heap with their end days
        while i < n and events[i][0] == day:
            heapq.heappush(min_heap, events[i][1])
            i += 1
        
        # Remove events that have already ended (end day before current day)
        while min_heap and min_heap[0] < day:
            heapq.heappop(min_heap)
        
        # If there is an available event, attend the one ending earliest
        if min_heap:
            heapq.heappop(min_heap)
            total_events += 1
            
    return total_events

# Example usage:
# events = [[1,2],[2,3],[3,4]]
# print(maxEvents(events))  # Expected Output: 3
← Back to All Questions