Today's algorithm is theMaximum Number of Events problem:

Given an array of events whereevents[i] = [startDayi, endDayi]. Every eventi starts atstartDayi and ends atendDayi. You can attend an eventi at any dayd wherestartTimei <= d <= endTimei. Notice that you can only attend one event at any timed. 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 be4, 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 theevents 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 dayhas 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 theevents 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.

functionmaxEvents(events){if(events.length<2)returnevents.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 callunique. At the very end of the function, we canreturn unique.size..size is a method for sets which returns the number of elements in the set.

functionmaxEvents(events){if(events.length<2)returnevents.lengthevents.sort((a,b)=>a[1]-b[1])letunique=newSet()//...returnunique.size;}

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

The outer for loop will iterate from0 toevents.length, whereas the inner for loop will iterate fromevents[i][0] toevents[i][1].

functionmaxEvents(events){if(events.length<2)returnevents.lengthevents.sort((a,b)=>a[1]-b[1])letunique=newSet()for(leti=0;i<events.length;i++){for(letj=events[i][0];j<=events[i][1];j++){//...}}returnunique.size;}

Inside these nested loops, we want to check ifunique has already seen the date. The date is accessed through the value ofj. We can check if a value is in a set by calling.has() onunique, and passing inj. 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.

functionmaxEvents(events){if(events.length<2)returnevents.lengthevents.sort((a,b)=>a[1]-b[1])letunique=newSet()for(leti=0;i<events.length;i++){for(letj=events[i][0];j<=events[i][1];j++){if(!unique.has(j)){//...}}}returnunique.size;}

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

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 callingbreak inside the inner loop, the inner loop will stop executing, and the outer loop will increment. We want to callbreak once we add a value tounique 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 tounique, 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.

functionmaxEvents(events){if(events.length<2)returnevents.lengthevents.sort((a,b)=>a[1]-b[1])letunique=newSet()for(leti=0;i<events.length;i++){for(letj=events[i][0];j<=events[i][1];j++){if(!unique.has(j)){unique.add(j);break;}}}returnunique.size;}

--

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