The Maximum Number of Events Problem

Today's algorithm is the Maximum Number of Events problem:

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi. You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d. Return the maximum number of events you can attend.

Let's say we had a calendar for a four day week. The calendar is full of events, which each can span multiple days. Each color block represents an event:

You don't have to go to each event every day--you can go to one day of a three day event. If you wanted to maximize the number of events you go to, you'd break up your calendar like this, where you'd only go to the events on the darkly shaded days:

This way, you can go to all four events! This algorithm is asking you to write a function that computes that. If you were to turn the above calendar into an array of events, where the first elements is the start day and the second element is the end day, you'd get [[1, 3], [2, 4], [4, 5], [2, 3]]. The function's output should be 4, because that's the maximum number of events you can go to.

This problem is very tricky. There's a few ways to solve it, and if you write in a language like Java you can use Priority Queues. However, in this post I'll go over a solution to this that's written in JavaScript and uses sets.

Approaching the Problem

A set is useful in this problem because it keeps track of unique numbers. You can't have duplicates in a set, which means you can quickly look up to see if a value has already been seen.

To make use of sets, we'll want to order the inputted events, sorting them by end day: the events with the earlier end days will come first in the events array, and the events with the later end days will come last in the array. We'll then create nested for loops, which will initially just check the start day of each event. If that start day hasn't yet been seen in the set, we'll add that day to the set--in other words, we want to keep track of every unique starting day. If that start day has been seen in the set, we'll want to check the end day--if the end day hasn't been seen yet, and therefore isn't in the set, then we can add it to the set. By the end, we'll just return the size of the set.

I think this is the kind of problem that's harder to explain in words without also coding the solution, so I'll just jump into it.

Coding the Solution

We'll start by checking for base cases -- if the events array has 1 event in it, then the maximum number of events we can go to is 1. If the array has no events, then the maximum number is 0.

function maxEvents(events) {
    if (events.length < 2) return events.length
    //...
}

We'll then sort the array, using .sort(), passing in a callback function which will order the events by end day. Since the event arrays are [startDay, endDay], and arrays are 0 indexed, we know the end day is at index 1. To sort something in an increasing order using .sort(), we can pass in the function (a,b) => a - b -- but in the case, since we're interested in sorting by end time, we'll pass in (a,b) => a[1] - b[1].

We'll also want to initialize a set, which we'll call unique. At the very end of the function, we can return unique.size. .size is a method for sets which returns the number of elements in the set.

function maxEvents(events) {
    if (events.length < 2) return events.length
    events.sort((a,b) => a[1] - b[1])
    let unique = new Set()
    //...
    return unique.size;
}

We'll now want to create two nested for loops. The first, outer, for loop will check each event in the events array. The second, inner, for loop will check each day within each event.

The outer for loop will iterate from 0 to events.length, whereas the inner for loop will iterate from events[i][0] to events[i][1].

function maxEvents(events) {
    if (events.length < 2) return events.length
    events.sort((a,b) => a[1] - b[1])
    let unique = new Set()
    for (let i = 0; i < events.length; i++) {
        for (let j = events[i][0]; j <= events[i][1]; j++) {
            //...
        }
    }
    return unique.size;
}

Inside these nested loops, we want to check if unique has already seen the date. The date is accessed through the value of j. We can check if a value is in a set by calling .has() on unique, and passing in j. We can put the not operator ! in front of this, because we're only interested in instances where the value has NOT been seen in the set.

function maxEvents(events) {
    if (events.length < 2) return events.length
    events.sort((a,b) => a[1] - b[1])
    let unique = new Set()
    for (let i = 0; i < events.length; i++) {
        for (let j = events[i][0]; j <= events[i][1]; j++) {
            if (!unique.has(j)) {
                //...
            }
        }
    }
    return unique.size;
}

If that date hasn't been seen in the set unique, then we'll want to add it using .add, passing in j.

At this point, we're nearly done -- we're checking every date, seeing if it's already been found in another event, and adding it to the calendar if it hasn't. There's one last piece to this function that we should add: break.

When it's called, a break statement jumps out of a loop. That means that, by calling break inside the inner loop, the inner loop will stop executing, and the outer loop will increment. We want to call break once we add a value to unique because we don't want to add every event's end date: if a start date hasn't been seen before, we want to add it to unique, but we don't need to check the end date.

The reason for why we need a break statement can be seen with an example. Let's say the events array was [[1, 2], [2, 3]]. If we didn't have a break statement, then the function would add every unique date--both start date and end date--to a set. By the end of the function, the set would be {1, 2, 3}, which has a size of 3--but by looking at the array, we know there's no way we could go to three events. By only checking the end date if the start date isn't unique, we prevent errors like this one.

function maxEvents(events) {
    if (events.length < 2) return events.length
    events.sort((a,b) => a[1] - b[1])
    let unique = new Set()
    for (let i = 0; i < events.length; i++) {
        for (let j = events[i][0]; j <= events[i][1]; j++) {
            if (!unique.has(j)) {
                unique.add(j);
                break;
            }
        }
    }
    return unique.size;
}

--

Let me know in the comments if you have questions or alternate solutions!