Interval Scheduling Algorithm

Welcome back! In our previous lesson, we saw how sorting intervals by their start times was the key to efficiently merging overlapping intervals. This sort -> iterate -> decide pattern is incredibly powerful, and today we'll see it in action again, but with a crucial twist.

This lesson focuses on a classic problem known as the Activity Selection Problem. Imagine you have a list of potential activities, each with a start and end time, and you want to participate in as many as possible. Since you can only do one at a time, you need to pick a subset of activities that don't overlap. Our goal is to find the largest possible set of compatible activities.

You'll discover that a simple change in our sorting strategy—from sorting by start times to sorting by end times—unlocks an elegant and optimal greedy solution for this new problem.

The Problem: Maximizing Non-Overlapping Activities

Let's formalize this. Given a collection of intervals, we want to select the maximum number of intervals such that no two selected intervals overlap. For example, given [[1,3], [2,4], [3,5]], you could select [1,3] and [3,5]. They only touch at the boundary, which is allowed. This gives you a set of two activities. You couldn't select [1,3] and [2,4] because they overlap. The maximum number of non-overlapping activities is 2.

This problem is often presented as finding the minimum number of intervals to remove to make the rest non-overlapping (like in LeetCode #435, "Non-overlapping Intervals"). These are two sides of the same coin: if you find the maximum number of activities you can keep, let's say k, out of n total activities, then the minimum number you must remove is simply n - k.

So, how do we find this maximum set? Let's explore some greedy strategies.

The Greedy Choice: Why Sorting by End Time Wins

In our last lesson, sorting by start time worked beautifully. What if we try that here?
Consider the intervals [[1, 100], [2, 5], [3, 6]].

• If we sort by start time and pick the first one, [1, 100], we're done. We can't pick any others. Our total is 1.
• However, the optimal solution is [2, 5] and [3, 6], which would be missed. Our total should be 2.

Clearly, sorting by start time isn't the right greedy choice here. The problem is that a very long interval that starts early can block out many shorter, more compatible intervals.

What about picking the shortest interval first? This also seems plausible but can fail. Consider [[4, 7], [1, 5], [6, 10]].

• The shortest interval is [4, 7]. If we pick it, we block both [1, 5] and [6, 10]. Our total is 1.
• The optimal solution is to pick [1, 5] and [6, 10]. Our total is 2.

This brings us to the winning strategy: always pick the interval that finishes earliest.

The intuition is powerful: by selecting the activity that finishes as soon as possible, we free up our time, maximizing the opportunity to fit in more activities later. Think of it like scheduling meetings in a single conference room. To maximize the number of meetings, you should always give preference to the meeting that ends first, because it makes the room available again sooner.

The following resource provides an excellent explanation of this intuition.

The Algorithm in Action

With our greedy strategy chosen, the algorithm becomes straightforward:

1. Sort all intervals based on their end times in ascending order.
2. Select the first interval in the sorted list. This is our first activity. Let's keep track of its finish time, last_finish_time.
3. Iterate through the rest of the sorted intervals. For each interval:
   • If its start_time is greater than or equal to last_finish_time, it means this activity starts after (or exactly when) our last chosen activity finished. It doesn't overlap!
   • So, we select this new interval and update last_finish_time to its end time.
   • If it does overlap (i.e., its start_time is less than last_finish_time), we simply ignore it and move on.

The image below provides a perfect visual walkthrough of this process. The activities are pre-sorted by their finish times.

Let's trace the steps shown in the diagram:

1. Assume we've already sorted the intervals by finish time. We start with an imaginary activity that ends at time 0.
2. The first activity we consider is A[0]. It starts after time 0, so we select it. Our set is now {0}. The last finish time is f[0].
3. We scan forward, skipping A[1] and A[2] because they start before f[0].
4. The next compatible activity is A[3], which starts after f[0] (actually, it looks like it starts after f[1] in this diagram, implying we picked A[1] first, but let's stick to the principle. The diagram's text says "select the first activity i with s[i] > f[1]" after A[1] is chosen. Let's correct the trace based on the image's annotations which are slightly different from the general algorithm but illustrate the same idea).
   • Let's follow the image's logic more closely: It seems to pick A[0], then looks for the next activity starting after f[0]. Let's assume that is A[3]. (The annotations s[i] > f[1] and s[i] > f[3] are slightly confusing, let's follow the main principle).
   • Let's trace it our way, which is clearer:
     1. Sort by finish times. Let's assume the intervals in the image A[0]...A[8] are already sorted this way.
     2. Select A[0]. last_finish_time is f[0].
     3. A[1] starts before f[0] ends. Skip. A[2] starts before f[0] ends. Skip.
     4. A[3] starts after f[0] ends. Select A[3]. Update last_finish_time to f[3]. Our set is {0, 3}.
     5. A[4] starts before f[3] ends. Skip.
     6. A[5] starts after f[3] ends. Select A[5]. Update last_finish_time to f[5]. Our set is {0, 3, 5}.
     7. A[6] and A[7] start before f[5] ends. Skip.
     8. A[8] starts after f[5] ends. Select A[8]. Update last_finish_time to f[8]. Our set is {0, 3, 5, 8}.

This gives us the final set of 4 activities, which is the maximum possible.

For a dynamic walkthrough, the following video explains and visualizes the process clearly.

Why Is This Greedy Choice Optimal?

We have strong intuition that this works, but how can we be sure it's always optimal? For this, we can use a technique called an exchange argument. You don't need to write formal proofs in an interview, but having a solid "correctness argument" is a huge plus.

The argument goes like this:

1. Let G be the set of activities selected by our greedy algorithm (sorted by finish time).
2. Let O be any optimal solution.
3. Compare the first activity in G (g_1) and O (o_1). By our rule, g_1 must finish no later than o_1.
4. If g_1 is the same as o_1, great. We move to the next activity.
5. If they are different, we can "exchange" o_1 for g_1 in the optimal solution. Since g_1 finishes earlier, it won't conflict with any subsequent activities in O that o_1 didn't. The new "optimal" solution is still valid and has the same size.
6. By repeating this process, we can transform any optimal solution into our greedy solution, one activity at a time, without ever decreasing its size. This implies our greedy solution must have the same size as any optimal solution. Therefore, it is optimal.

This concept can be a bit abstract. The following video provides one of the clearest explanations of this proof available.

Implementation in TypeScript

Now, let's translate this into TypeScript. We will implement the version that finds the maximum number of non-overlapping intervals you can keep.

function maxNonOverlappingIntervals(intervals: number[][]): number {
    if (intervals.length === 0) {
        return 0;
    }

    // 1. Sort intervals by their END times
    intervals.sort((a, b) => a[1] - b[1]);

    // 2. Select the first interval and initialize count
    let count = 1;
    let lastFinishTime = intervals[0][1];

    // 3. Iterate through the rest of the intervals
    for (let i = 1; i < intervals.length; i++) {
        const currentStartTime = intervals[i][0];

        // 4. If there's no overlap, select this interval
        if (currentStartTime >= lastFinishTime) {
            count++;
            lastFinishTime = intervals[i][1];
        }
        // 5. If there is an overlap, do nothing and let the loop continue
    }

    return count;
}

// Example usage for a problem asking for minimum removals:
function eraseOverlapIntervals(intervals: number[][]): number {
    const maxKept = maxNonOverlappingIntervals(intervals);
    return intervals.length - maxKept;
}

This implementation directly follows our algorithm. A crucial detail is the overlap check: currentStartTime >= lastFinishTime. The >= is important because intervals that touch at their boundaries (e.g., [1,3] and [3,5]) are considered non-overlapping.

For a final review of the implementation details and common pitfalls, the following resources are excellent.

Conclusion

Today we tackled the Activity Selection problem and found a powerful greedy solution. By sorting intervals by their finish times, we ensure that our local choice—picking the activity that ends earliest—is also a globally optimal one. This maximizes the available time for subsequent activities.

Here are the key takeaways:

• The Greedy Choice Matters: Unlike the Merge Intervals problem where we sorted by start times, here we must sort by end times. The problem's goal dictates the correct sorting criterion.
• Intuition: The "earliest finish time" strategy works because it frees up resources sooner, creating maximum opportunity for what comes next.
• Algorithm: The sort-by-end-time -> iterate -> select-if-compatible pattern is efficient, running in $O(n\log n)$ time due to the sort.
• Problem Variants: Be mindful of whether a problem asks for the maximum number of intervals to keep or the minimum to remove. The underlying algorithm is the same, but the final return value changes.

In our next lesson, we will explore another interval-based problem: determining the minimum number of resources (like meeting rooms) needed to accommodate a set of overlapping time intervals. This will introduce yet another classic pattern and a new data structure to help us solve it efficiently.