Calculating Minimum Resource Requirements

Welcome back. In our last lesson, we focused on a selection problem: how to pick the maximum number of non-overlapping activities for one person to attend. We discovered that sorting by end times was the key to a successful greedy strategy.

Today, we'll continue exploring interval problems, but from a different perspective. Instead of being the attendee, imagine you are the facility manager. You have a list of all requested meetings and their time slots. Your job isn't to select a few, but to accommodate all of them. Your goal is to figure out the absolute minimum number of conference rooms you need to make this happen. This lesson will teach you how to determine the minimum number of concurrent resources required for a given set of time intervals. You'll learn a powerful and elegant technique that, once again, leverages sorting to find the answer efficiently.

From Selection to Allocation

The problem we're tackling is often called "Meeting Rooms II" or the "Minimum Platforms" problem. The core question is always the same: what is the maximum number of events happening at the same time? This peak overlap determines the minimum number of resources (rooms, platforms, servers, etc.) you must have available.

Consider the intervals shown in the image below. At time t=11, three different intervals are active. This moment of maximum overlap tells us we need at least three resources.

Our goal is to find this peak number algorithmically. The fundamental idea is to track the number of active events over time. This count increases whenever an event starts and decreases whenever an event ends. We just need to find the highest value this count ever reaches.

The video below introduces this core concept with a clear, visual example.

The Sweep-Line Approach: Tracking Events Chronologically

How can we systematically track the starts and ends to find the peak overlap? Imagine a "sweep-line" moving across the timeline from left to right. We just need to process events in the order they occur.

This idea of processing events in chronological order is the foundation of our algorithm. But how do we implement it efficiently? Instead of looking at every single point in time (which could be infinite!), we only need to consider the moments when something changes: the start and end times of the intervals.

A highly effective way to do this is to deconstruct our intervals into separate start and end points, sort them, and then process them in order. This leads to an elegant two-pointer solution.

The Two-Pointer Algorithm

Here is the most common and efficient approach to solve this problem:

1. Deconstruct and Sort: Create two separate arrays. One containing all the start times and another containing all the end times. Sort both of these arrays independently in ascending order.
2. Initialize Pointers and Counters:
   • Set up two pointers, s_ptr at the beginning of the start times array and e_ptr at the beginning of the end times array.
   • Initialize rooms = 0 (current rooms in use) and maxRooms = 0 (the peak we've seen so far).
3. Iterate and Compare: Loop as long as you still have start times to process (i.e., s_ptr is within bounds). In each step of the loop, compare the next available start time with the next available end time:
   • If starts[s_ptr] < ends[e_ptr]: This means a new meeting is starting before the earliest-ending current meeting has finished. We need an additional room. So, increment rooms and advance the start pointer (s_ptr++).
   • Else (if starts[s_ptr] >= ends[e_ptr]): This means a meeting has finished (or is finishing at the exact same moment a new one begins). A room is freed up. So, decrement rooms and advance the end pointer (e_ptr++).
4. Track the Maximum: After each change to the rooms count, update maxRooms = Math.max(maxRooms, rooms).
5. Return: The final value of maxRooms is your answer.

The following videos walk through this exact logic. The first one, from NeetCode, continues from where we left off and explains the two-pointer approach in detail. The second one, from Anuj Kumar Sharma, presents the same algorithm but in the context of trains and platforms, which can help solidify the concept.

The image below provides a static trace of this algorithm for a simple train schedule problem. You can see how the pointers i (for arrivals/starts) and j (for departures/ends) move, and how the Platform and max Platform counts are updated at each step.

Implementation in TypeScript

Let's translate this two-pointer logic into a clean TypeScript function.

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

    // 1. Deconstruct and Sort
    const startTimes = intervals.map(interval => interval[0]).sort((a, b) => a - b);
    const endTimes = intervals.map(interval => interval[1]).sort((a, b) => a - b);

    // 2. Initialize Pointers and Counters
    let startPointer = 0;
    let endPointer = 0;
    let rooms = 0;
    let maxRooms = 0;

    // 3. Iterate while there are meetings left to start
    while (startPointer < intervals.length) {
        // Compare next start time with next end time
        if (startTimes[startPointer] < endTimes[endPointer]) {
            // A new meeting starts before one ends, need a new room.
            rooms++;
            startPointer++;
        } else {
            // A meeting ends, freeing up a room.
            // This also handles the case where a meeting starts exactly when another ends.
            // We process the 'end' first, reusing the room.
            rooms--;
            endPointer++;
        }
        
        // 4. Track the Maximum
        maxRooms = Math.max(maxRooms, rooms);
    }

    // 5. Return the peak number of rooms required
    return maxRooms;
}

// Example:
const meetings = [[0, 30], [5, 10], [15, 20]];
console.log(minMeetingRooms(meetings)); // Output: 2

const meetings2 = [[7,10], [2,4]];
console.log(minMeetingRooms(meetings2)); // Output: 1

Alternative Approaches and Considerations

While the two-pointer method is very efficient, it's useful to be aware of other ways to solve this.

1. Min-Heap Approach

Another popular solution involves sorting the intervals by their start times and using a min-heap (or priority queue) to keep track of the end times of ongoing meetings.

• Iterate through the sorted intervals.
• For each meeting, check the earliest end time in the heap (the top element). If the current meeting starts after or at the same time as this earliest end time, it means a room has freed up. You can pop from the heap.
• Then, add the current meeting's end time to the heap.
• The maximum size the heap ever reaches during this process is the answer.

You can read more about this in the "Min Heap" section of the following resource. We'll be covering heaps in detail later in the course, so for now, you only need to understand the concept.

2. Difference Array (Chronological Booking)

A third method, often called chronological booking or using a difference array, involves creating a timeline array. You increment the value at a start time and decrement it at an end time. Then, you compute a prefix sum across this timeline; the maximum value of the prefix sum is your answer.

The key takeaway is that the two-pointer and min-heap approaches are generally preferred because their space complexity depends on the number of intervals (O(n)), not on the magnitude of the time values (O(max_end_time)).

Conclusion

In this lesson, we solved the problem of finding the minimum resources needed for a set of time-based events. We established that this is equivalent to finding the point of maximum concurrent overlap.

Here are the key takeaways:

• The Core Problem: Minimum resources = maximum simultaneous events.
• The Sweep-Line Intuition: The number of active events only changes at start and end times. We can find the peak by processing these "change points" in chronological order.
• Two-Pointer Algorithm: A very efficient method is to separate start and end times into two sorted arrays and use two pointers to simulate the sweep-line, tracking the current number of active events.
• Handling Ties: When a start and end time are equal, processing the end event first allows for resource reuse and correctly prevents over-counting. The condition start < end vs. start >= end handles this naturally.

You've now seen two powerful sort -> iterate patterns for interval problems. In the last lesson, sorting by end time helped us select a maximal non-overlapping set. Today, sorting start and end times separately helped us count the maximal overlap.

In our next lesson, we will tackle a different type of greedy problem related to reachability, often seen in questions like "Jump Game". You'll learn how to solve it by always maintaining the "farthest position reached so far".