loading...

The Maximum Number of Events Problem

alisabaj profile image Alisa Bajramovic ・5 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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:

Four day calendar with events. First event is red and is on days 1 and 2. Second event is blue and is on days 2 and 3. Third event is green and is on day 4. Fourth event is pink and is on day 2.

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:

Same calendar as above, except the first event (in red) is opaque on day 2, and the second event (in blue) is opaque on day 2.

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!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide