Maximum Number of Events That Can Be Attended

Medium Heaps Advanced Original on LeetCode

Maximum Number of Events That Can Be Attended is a medium heaps problem solved with the advanced pattern. The best approach, optimal (day sweep with a min-heap of end days), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (earliest deadline, scan for a free day) up.

Problem

You are given a list events where events[i] = [start_i, end_i] means event i can be attended on any single whole day d with start_i <= d <= end_i.

You can attend at most one event per day, and attending an event takes just one day of its range. Return the maximum number of events you can attend.

Examples

Example 1

Input
events = [[1, 2], [1, 2], [1, 2]]
Output
2
Why
Only days 1 and 2 exist for these three events, so at most two of them can be attended.

Example 2

Input
events = [[2, 4], [1, 1], [1, 3], [3, 3]]
Output
4
Why
Go to [1, 1] on day 1, [1, 3] on day 2, [3, 3] on day 3 and [2, 4] on day 4.

Example 3

Input
events = [[5, 5], [1, 10]]
Output
2
Why
Attend [1, 10] on any day except 5 and [5, 5] on day 5.

Constraints

  • 1 <= events.length <= 10^5
  • events[i].length == 2
  • 1 <= start_i <= end_i <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (earliest deadline, scan for a free day)O(n log n + n · D)O(D)
Optimal (day sweep with a min-heap of end days)O(n log n)O(n)

1Brute force (earliest deadline, scan for a free day)

TimeO(n log n + n · D)Sorting, then each event may scan its whole range of up to D = 10^5 days.
SpaceO(D)One flag per day.

Handle events in order of end day. Give each one the earliest day in its range that is still free, scanning day by day. Events that end sooner have fewer choices, so serving them first and taking the earliest free day never blocks a better schedule.

  1. Sort events by end day (ties by start day).
  2. used = boolean array over days.
  3. For each event, scan d from start to end; at the first free d, mark it used, count++ and stop.
class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        boolean[] used = new boolean[100002];
        int count = 0;
        for (int[] e : events) {
            for (int d = e[0]; d <= e[1]; d++) {
                if (!used[d]) {
                    used[d] = true;
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

2Optimal (day sweep with a min-heap of end days)

TimeO(n log n)Sorting plus one push and at most one pop per event; days with no open event are skipped.
SpaceO(n)The heap can hold every event at once.

Sweep the days in increasing order. When a day arrives, push the end day of every event that starts on it into a min-heap, drop ends that are already in the past, and attend the open event that ends soonest. When the heap is empty, jump straight to the next start day.

  1. Sort events by start day; i = 0, day = 0, count = 0.
  2. While i < n or the heap is not empty: if the heap is empty, set day to events[i] start.
  3. Push the end of every event with start == day (advance i).
  4. Pop ends smaller than day. If the heap is still non-empty, pop one, count++.
  5. day++ and repeat.
class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> ends = new PriorityQueue<>();
        int n = events.length, i = 0, day = 0, count = 0;
        while (i < n || !ends.isEmpty()) {
            if (ends.isEmpty()) day = events[i][0];
            while (i < n && events[i][0] == day) ends.offer(events[i++][1]);
            while (!ends.isEmpty() && ends.peek() < day) ends.poll();
            if (!ends.isEmpty()) {
                ends.poll();
                count++;
            }
            day++;
        }
        return count;
    }
}

Edge cases to test

  • Many identical events squeezed into a short range
  • A long event and a one-day event that both want the same day
  • Gaps between events (days on which nothing is available)

Hints

Hint 1

On a given day, if several open events are available, which one is the most urgent to attend?

Hint 2

Pick the open event that ends soonest: it has the fewest days left to be used.

Hint 3

Sweep the days in order, add events as they open into a min-heap keyed by end day, and throw away the ones that have already ended.

FAQ

What is the best time complexity for Maximum Number of Events That Can Be Attended?

Optimal (day sweep with a min-heap of end days) runs in O(n log n) time and O(n) extra space. Sorting plus one push and at most one pop per event; days with no open event are skipped.

Which pattern does Maximum Number of Events That Can Be Attended use?

It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Find Median from Data Stream, Trapping Rain Water II.

Is there a brute force solution for Maximum Number of Events That Can Be Attended?

Yes. Brute force (earliest deadline, scan for a free day) takes O(n log n + n · D) time and O(D) space. Handle events in order of end day.

Which edge cases should I test for Maximum Number of Events That Can Be Attended?

Many identical events squeezed into a short range; A long event and a one-day event that both want the same day; Gaps between events (days on which nothing is available).