Jobs

Interviews

Discussions

Maximum Number of Events That Can Be Attended

Medium

Visa

0 views

Topics:

Greedy AlgorithmsArraysDynamic Programming

You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_iand ends at endDay_i.

You can attend an event i at any day d where startDay_i <= d <= endDay_i. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Constraints:

1 <= events.length <= 10⁵
events[i].length == 2
1 <= startDay_i <= endDay_i <= 10⁵

Maximum Number of Events That Can Be Attended

Medium

Visa

0 views

Topics:

Greedy AlgorithmsArraysDynamic Programming

You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_iand ends at endDay_i.

You can attend an event i at any day d where startDay_i <= d <= endDay_i. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Constraints:

1 <= events.length <= 10⁵
events[i].length == 2
1 <= startDay_i <= endDay_i <= 10⁵

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the start and end days of the events? Can they be zero, negative, or extremely large?
If multiple events are available on the same day, is there a preference for which event to attend (e.g., shortest duration, earliest end day)?
Is the input list of events sorted in any way (by start day, end day, duration, etc.)? If not, can I assume it's unsorted?
In the case where no events can be attended (e.g., all events overlap), what should the function return?
Can events have the same start and end day (i.e., a one-day event)? How should these be handled?

Brute Force Solution

Approach

The goal is to attend the maximum number of events given a list of events with start and end days. The brute force method involves exploring every possible combination of events, attending some and skipping others, to find the best possible schedule. It's like trying out every single choice until you find one that works best.

Here's how the algorithm would work step-by-step:

Consider the first event. You have two choices: either attend it or skip it.
If you attend the first event, mark all the days it occupies as busy, meaning you can't attend any other events happening on those days.
If you skip the first event, you're free to consider all other events without any restrictions from it.
Now, move on to the second event. Again, you have two choices: attend it or skip it. But, remember to check if the days of this event are already busy (if you chose to attend an earlier event).
Continue this process for all the events. At each event, decide whether to attend or skip, based on whether the event overlaps with previously attended events.
Keep track of how many events you've attended for each possible combination of choices (attend/skip for each event).
After exploring all possible combinations of attending and skipping events, compare all the scenarios you explored.
Choose the scenario where you attended the most events without any overlaps.

Code Implementation

def max_events_brute_force(events):
    max_attended_events = 0

    def solve(index, attended_events, busy_days):
        nonlocal max_attended_events

        if index == len(events):
            max_attended_events = max(max_attended_events, len(attended_events))
            return

        # Option 1: Skip the current event
        solve(index + 1, attended_events, busy_days)

        # Option 2: Attend the current event if possible
        start_day = events[index][0]
        end_day = events[index][1]

        can_attend = True
        for day in range(start_day, end_day + 1):
            if day in busy_days:
                can_attend = False
                break

        # Only proceed if the event doesn't overlap with busy days
        if can_attend:

            # Create a copy to avoid modifying the original list.
            new_busy_days = busy_days.copy()

            # Mark days as busy if attending this event
            for day in range(start_day, end_day + 1):
                new_busy_days.add(day)

            # Because we attended one more event we can add the new one
            solve(index + 1, attended_events + [index], new_busy_days)

    solve(0, [], set())
    return max_attended_events

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores every possible combination of attending or skipping events. For each event, there are two choices: attend or skip. Since there are 'n' events, the total number of combinations to explore is 2 * 2 * ... * 2 (n times), which is 2^n. Therefore, the algorithm's time complexity is exponential, driven by the need to evaluate each possible subset of events.

Space Complexity

O(2^N) – The brute force approach explores every possible combination of attending or skipping events. For N events, there are 2^N possible combinations. Each of these combinations requires storing a count of attended events and potentially a record of which days are busy. Therefore, the space needed to keep track of these scenarios grows exponentially with the number of events N, resulting in O(2^N) space complexity.

Optimal Solution

Approach

To maximize the number of events you can attend, focus on picking the events that end sooner rather than later. This frees up more time to attend other events. We'll use a method that prioritizes ending earlier while making sure we don't try to attend events that overlap in time.

Here's how the algorithm would work step-by-step:

First, imagine arranging all the events from earliest end date to latest end date.
Then, go through the events in that order, attending an event only if it doesn't overlap with any previously attended events.
Keep track of the days you've already attended events. If an event starts on or after the end date of the previously attended event, and you haven't attended an event that day, you can attend it.
Repeat this process until you've considered all events. The total number of events you've attended is the maximum number you can attend without any overlaps.

Code Implementation

def max_events_to_attend(events):
    events.sort(key=lambda x: x[1])

    attended_days = set()
    number_of_events_attended = 0

    # Iterate through events sorted by end date
    for start_day, end_day in events:
        for day in range(start_day, end_day + 1):
            # Check if the current day hasn't been attended yet
            if day not in attended_days:
                attended_days.add(day)

                # Increment event count if attended
                number_of_events_attended += 1
                break
    return number_of_events_attended

def max_events_to_attend_optimal(events):
    # Sort events by end date to prioritize earlier ending events.
    events.sort(key=lambda x: x[1])

    attended_days = set()
    max_events = 0

    for start_day, end_day in events:
        # Attempt to attend the event on the earliest possible day.
        for day in range(start_day, end_day + 1):
            # Attend if the day is available.
            if day not in attended_days:
                attended_days.add(day)
                max_events += 1
                break

    return max_events

def max_events(events):
    # Sort the events based on their end dates.
    events.sort(key=lambda x: x[1])

    attended_events = []

    # Iterate through each event in the sorted list.
    for event_start, event_end in events:
        can_attend = True

        # Check for overlaps with already attended events.
        for attended_start, attended_end in attended_events:
            if event_start <= attended_end and event_end >= attended_start:
                can_attend = False
                break

        # Add the event to the attended list if no overlap.
        if can_attend:
            attended_events.append((event_start, event_end))

    # Return the total number of events attended.
    return len(attended_events)

def max_events_attend(events):
    # Sort events based on their end day
    events.sort(key=lambda x: x[1])

    attended_days = set()
    event_count = 0

    # Iterate through sorted events
    for start_day, end_day in events:
        # Attempt to find a suitable day within the event's duration
        for day in range(start_day, end_day + 1):

            # If the day is not already attended, attend the event
            if day not in attended_days:

                # Mark the day as attended
                attended_days.add(day)
                event_count += 1
                break
    return event_count

def max_number_of_events(events):
    # Sort events by end date, prioritizing events finishing sooner.
    events.sort(key=lambda x: x[1])

    attended_days = set()
    max_possible_events = 0

    # Iterate through each event.
    for start_date, end_date in events:
        # Attempt to attend the event on the earliest possible day.
        for day in range(start_date, end_date + 1):
            # Check if the current day is available.
            if day not in attended_days:
                # Mark the day as attended.
                attended_days.add(day)

                # Increment the number of attended events.
                max_possible_events += 1
                break

    return max_possible_events

def max_events_that_can_be_attended(events):
    # Sort events by end date
    events.sort(key=lambda x: x[1])

    attended_dates = set()
    event_counter = 0

    # Iterate over events in sorted order
    for start_date, end_date in events:
        # Try to attend event on each day between start and end date
        for date in range(start_date, end_date + 1):
            # Attend the event if the date isn't taken
            if date not in attended_dates:
                attended_dates.add(date)
                event_counter += 1
                break
    return event_counter

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this solution is sorting the events by their end dates, which takes O(n log n) time, where n is the number of events. Iterating through the sorted events takes O(n) time. Inside the loop, checking for overlaps with previously attended events can take up to O(n) time in the worst case. However, since we are only comparing the current event start time to the end time of the previously attended event, this check effectively is O(1) since we are only checking one event. So we have sorting that takes O(n log n), iterating takes O(n), and the inside overlap check takes O(1). Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The provided solution description indicates a need to 'keep track of the days you've already attended events'. This implies the use of a data structure, such as a set or a boolean array, to store the attended days. In the worst-case scenario, if all events have distinct days, this data structure could potentially store up to N days, where N represents the number of events. Therefore, the auxiliary space used grows linearly with the number of events, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty event list	Return 0 immediately as no events can be attended.
Events with start day equal to end day	Treat these as valid single-day events.
Overlapping events	The algorithm needs to prioritize events to maximize attendance, for example using a greedy approach of selecting events that end earliest.
Large number of events (scalability)	Use efficient data structures and algorithms (e.g., priority queue and sorting) to avoid time complexity issues, ideally O(n log n).
Events with large start and end day values (integer overflow)	Ensure that the data type used for start and end days is large enough to accommodate all possible values, potentially using 64-bit integers if necessary.
Events with identical start and end days	The algorithm should handle duplicate events correctly as separate opportunities to attend an event on that day.
Events that span a very long duration	The algorithm should consider events with a very large duration, like from day 1 to day 10000, and the data structure (e.g., priority queue) should handle it effectively.
All events occur on the same day	The maximum number of events that can be attended is 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the start and end days of the events? Can they be zero, negative, or extremely large?
If multiple events are available on the same day, is there a preference for which event to attend (e.g., shortest duration, earliest end day)?
Is the input list of events sorted in any way (by start day, end day, duration, etc.)? If not, can I assume it's unsorted?
In the case where no events can be attended (e.g., all events overlap), what should the function return?
Can events have the same start and end day (i.e., a one-day event)? How should these be handled?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first event. You have two choices: either attend it or skip it.
If you attend the first event, mark all the days it occupies as busy, meaning you can't attend any other events happening on those days.
If you skip the first event, you're free to consider all other events without any restrictions from it.
Now, move on to the second event. Again, you have two choices: attend it or skip it. But, remember to check if the days of this event are already busy (if you chose to attend an earlier event).
Continue this process for all the events. At each event, decide whether to attend or skip, based on whether the event overlaps with previously attended events.
Keep track of how many events you've attended for each possible combination of choices (attend/skip for each event).
After exploring all possible combinations of attending and skipping events, compare all the scenarios you explored.
Choose the scenario where you attended the most events without any overlaps.

Code Implementation

def max_events_brute_force(events):
    max_attended_events = 0

    def solve(index, attended_events, busy_days):
        nonlocal max_attended_events

        if index == len(events):
            max_attended_events = max(max_attended_events, len(attended_events))
            return

        # Option 1: Skip the current event
        solve(index + 1, attended_events, busy_days)

        # Option 2: Attend the current event if possible
        start_day = events[index][0]
        end_day = events[index][1]

        can_attend = True
        for day in range(start_day, end_day + 1):
            if day in busy_days:
                can_attend = False
                break

        # Only proceed if the event doesn't overlap with busy days
        if can_attend:

            # Create a copy to avoid modifying the original list.
            new_busy_days = busy_days.copy()

            # Mark days as busy if attending this event
            for day in range(start_day, end_day + 1):
                new_busy_days.add(day)

            # Because we attended one more event we can add the new one
            solve(index + 1, attended_events + [index], new_busy_days)

    solve(0, [], set())
    return max_attended_events

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine arranging all the events from earliest end date to latest end date.
Then, go through the events in that order, attending an event only if it doesn't overlap with any previously attended events.
Keep track of the days you've already attended events. If an event starts on or after the end date of the previously attended event, and you haven't attended an event that day, you can attend it.
Repeat this process until you've considered all events. The total number of events you've attended is the maximum number you can attend without any overlaps.

Code Implementation

def max_events_to_attend(events):
    events.sort(key=lambda x: x[1])

    attended_days = set()
    number_of_events_attended = 0

    # Iterate through events sorted by end date
    for start_day, end_day in events:
        for day in range(start_day, end_day + 1):
            # Check if the current day hasn't been attended yet
            if day not in attended_days:
                attended_days.add(day)

                # Increment event count if attended
                number_of_events_attended += 1
                break
    return number_of_events_attended

def max_events_to_attend_optimal(events):
    # Sort events by end date to prioritize earlier ending events.
    events.sort(key=lambda x: x[1])

    attended_days = set()
    max_events = 0

    for start_day, end_day in events:
        # Attempt to attend the event on the earliest possible day.
        for day in range(start_day, end_day + 1):
            # Attend if the day is available.
            if day not in attended_days:
                attended_days.add(day)
                max_events += 1
                break

    return max_events

def max_events(events):
    # Sort the events based on their end dates.
    events.sort(key=lambda x: x[1])

    attended_events = []

    # Iterate through each event in the sorted list.
    for event_start, event_end in events:
        can_attend = True

        # Check for overlaps with already attended events.
        for attended_start, attended_end in attended_events:
            if event_start <= attended_end and event_end >= attended_start:
                can_attend = False
                break

        # Add the event to the attended list if no overlap.
        if can_attend:
            attended_events.append((event_start, event_end))

    # Return the total number of events attended.
    return len(attended_events)

def max_events_attend(events):
    # Sort events based on their end day
    events.sort(key=lambda x: x[1])

    attended_days = set()
    event_count = 0

    # Iterate through sorted events
    for start_day, end_day in events:
        # Attempt to find a suitable day within the event's duration
        for day in range(start_day, end_day + 1):

            # If the day is not already attended, attend the event
            if day not in attended_days:

                # Mark the day as attended
                attended_days.add(day)
                event_count += 1
                break
    return event_count

def max_number_of_events(events):
    # Sort events by end date, prioritizing events finishing sooner.
    events.sort(key=lambda x: x[1])

    attended_days = set()
    max_possible_events = 0

    # Iterate through each event.
    for start_date, end_date in events:
        # Attempt to attend the event on the earliest possible day.
        for day in range(start_date, end_date + 1):
            # Check if the current day is available.
            if day not in attended_days:
                # Mark the day as attended.
                attended_days.add(day)

                # Increment the number of attended events.
                max_possible_events += 1
                break

    return max_possible_events

def max_events_that_can_be_attended(events):
    # Sort events by end date
    events.sort(key=lambda x: x[1])

    attended_dates = set()
    event_counter = 0

    # Iterate over events in sorted order
    for start_date, end_date in events:
        # Try to attend event on each day between start and end date
        for date in range(start_date, end_date + 1):
            # Attend the event if the date isn't taken
            if date not in attended_dates:
                attended_dates.add(date)
                event_counter += 1
                break
    return event_counter

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty event list	Return 0 immediately as no events can be attended.
Events with start day equal to end day	Treat these as valid single-day events.
Overlapping events	The algorithm needs to prioritize events to maximize attendance, for example using a greedy approach of selecting events that end earliest.
Large number of events (scalability)	Use efficient data structures and algorithms (e.g., priority queue and sorting) to avoid time complexity issues, ideally O(n log n).
Events with large start and end day values (integer overflow)	Ensure that the data type used for start and end days is large enough to accommodate all possible values, potentially using 64-bit integers if necessary.
Events with identical start and end days	The algorithm should handle duplicate events correctly as separate opportunities to attend an event on that day.
Events that span a very long duration	The algorithm should consider events with a very large duration, like from day 1 to day 10000, and the data structure (e.g., priority queue) should handle it effectively.
All events occur on the same day	The maximum number of events that can be attended is 1.