Maximum Number of Events That Can Be Attended

Ah, the age-old dilemma: how to maximize your social calendar without turning into a hermit. Imagine you’re juggling a series of events, each with its own start and end dates, and you want to attend as many as possible. Sounds like a fun party, right? But wait! You can’t be in two places at once, and you definitely don’t want to miss out on that epic taco festival just because you were stuck at a boring seminar.

Welcome to the Maximum Number of Events That Can Be Attended problem! In this LeetCode challenge, you’ll be tasked with figuring out how to attend the maximum number of events without overlapping schedules. Think of it as a game of Tetris, but instead of blocks, you’re fitting in social events.

Links to Other Solutions

Code Solution


class Solution {
  public int maxEvents(int[][] events) {
    int ans = 0;
    int d = 0; // the current day
    int i = 0; // events' index
    Queue minHeap = new PriorityQueue<>();

    Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));

    while (!minHeap.isEmpty() || i < events.length) {
      if (minHeap.isEmpty())
        d = events[i][0];
      while (i < events.length && events[i][0] == d)
        minHeap.offer(events[i++][1]);
      minHeap.poll();
      ++ans;
      ++d;
      while (!minHeap.isEmpty() && minHeap.peek() < d)
        minHeap.poll();
    }

    return ans;
  }
}

Approach Explanation

The code above employs a greedy algorithm to tackle the problem. Here’s a brief breakdown of the approach:

Sorting Events: First, we sort the events based on their start times. This allows us to efficiently manage which events are available to attend on any given day.
Using a Min-Heap: We utilize a min-heap (priority queue) to keep track of the end times of the events that are available to attend. This helps us always pick the event that ends the earliest, maximizing our chances of attending more events.
Iterating Through Days: We iterate through each day, checking if there are any events to attend. If there are, we attend the one that ends the soonest and then move on to the next day.
Skipping Over Events: If an event can’t be attended because it has already ended, we simply remove it from our heap and continue.

Time and Space Complexity

Time Complexity: O(n log n), where n is the number of events. This is due to the sorting step and the operations on the priority queue.

Space Complexity: O(n), as we may need to store all events in the priority queue.

Real-World Example

Imagine you’re a social butterfly with a calendar full of events: a yoga class, a book club meeting, and a taco festival (because who doesn’t love tacos?). You can only attend one event per day, and you want to make sure you hit the taco festival. By applying the logic from our solution, you can maximize your attendance at these events without missing out on the best taco truck in town!