Start learning free

LESSON 330 OF 348 · GREEDY

Meeting Rooms II in TypeScript: Sweep Line, O(n log n)

Practice O(n log n) Read the full explanation

Given an array consisting of meeting time intervals, which are represented by the start and end times ([s0, e0], [s1, e1], ...], determine the minimum number of meeting rooms needed in order to be able to accomodate all meetings at every moment of time.


Example:

Input: [[5, 10], [0, 30], [15, 20]]
Output: 2
Explanation: 1st and 3rd meetings can be assigned to the first room
             2nd meeting can be assigned to room 2

 

Note:

  1. You may assume the interval's end point is always greater than its start point.
  2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap.

Your algorithm should run in O(n log n) time and use O(n) extra space.


STEP 1 OF 10
    Ctrl + Enter to check

    TYPESCRIPT · GREEDY

    Meeting Rooms in TypeScript, explained

    Problem overview

    The method meetingRooms(intervals) receives meetings as [start, end] pairs and returns the smallest number of rooms that can hold all of them, so that no two meetings in the same room overlap. A meeting that ends at the exact moment another starts doesn't overlap it: [1, 2] and [2, 3] can share a room.

    For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meeting [0, 30] lasts the whole time, so it needs its own room. The other two don't overlap each other, so they can share the second room. The statement asks for O(n log n) time and O(n) extra space.

    Approach: count the meetings in progress

    The number of rooms you need equals the largest number of meetings happening at the same moment. Checking every moment is not possible, but the count only changes when a meeting starts or ends, so only those moments matter.

    Turn each meeting into two events: a start tagged 1 and an end tagged -1. Sort the events by time and sweep through them, keeping a running total. A start adds 1 to the number of meetings in progress, an end subtracts 1, and the largest total seen is the answer.

    Trace of the example. The events sorted by time are: 0 start, 5 start, 10 end, 15 start, 20 end, 30 end. The running total goes 1, 2, 1, 2, 1, 0. Its maximum is 2.

    When two events share the same time, the order decides the answer. If a meeting ends at 2 and another starts at 2, the end must be handled first, so that the room is freed before it is needed again. Sorting ties by the tag puts -1 ahead of 1. With [[1, 2], [2, 3]], the events at time 2 are [2, -1] and [2, 1]; handled in that order, the total never goes above 1. In the opposite order it would reach 2, which wrongly asks for a second room.

    Step by step

    1. Create the event list. Declare events as an empty number[][]. Each event is a pair of a time and a tag.
    2. Loop over the meetings with for...of and destructure each into start and end.
    3. Push the start event [start, 1].
    4. Push the end event [end, -1], as one pair.
    5. Sort the events with a comparator. When the times are equal, order by the tag with a[1] - b[1], so ends come first. Otherwise order by time with a[0] - b[0].
    6. Set up the counters. noOfMeetings counts meetings in progress and answer keeps the maximum, both starting at 0.
    7. Loop over the sorted events and destructure each into time and type.
    8. Add the tag to noOfMeetings. The values 1 and -1 turn the start or end decision into a single addition.
    9. Track the maximum with Math.max(answer, noOfMeetings).
    10. Return answer after the loop, once every event has been processed.

    The solution in TypeScript

    class Solution {
    meetingRooms(intervals: number[][]): number {
        const events: number[][] = [];
        for (const [start, end] of intervals) {
            events.push([start, 1]);
            events.push([end, -1]);
        }

        events.sort((a, b) => {
            if (a[0] === b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        let answer = 0, noOfMeetings = 0;
        for (const [time, type] of events) {
            noOfMeetings += type;
            answer = Math.max(answer, noOfMeetings);
        }

        return answer;
    }
}

    TypeScript details worth knowing:

    • Annotate the empty array. An empty array literal has no elements to infer from, so const events: number[][] = [] tells the compiler what it will hold. const only fixes the variable, and push still works.
    • Destructuring in for...of. for (const [start, end] of intervals) unpacks each pair into two names. Each iteration creates new bindings, which is why const is allowed in the loop header. In the second loop, time is unpacked but not used; the sort has already placed events in time order.
    • The comparator is required. Without one, sort converts each element to a string and compares text. For these events, sort() puts [5, 1] after [30, -1], since "5,1" comes after "30,-1" alphabetically. The sweep would then see events out of time order.
    • Ties in the comparator. === compares the times without type conversion. Sorting by time alone would leave tied events in their original order, which is the order they were pushed in, so a start could come before an end at the same time.
    • One let for two counters. let answer = 0, noOfMeetings = 0 declares both, and TypeScript infers number.
    • Types are erased. Annotations such as number[][] are checked while compiling and gone from the JavaScript that runs.

    Complexity

    Time: O(n log n). There are 2n events. Sorting them costs O(n log n) and the sweep costs O(n).

    Space: O(n). The event list holds two pairs per meeting. The input array isn't modified.

    Edge cases and common mistakes

    • No meetings. An empty list produces no events and the answer is 0.
    • Touching meetings. [[1, 2], [2, 3]] needs 1 room. Reversing the tie order, so that starts come first, would report 2.
    • Identical meetings. Three copies of [1, 5] need 3 rooms.
    • Nested meetings. [[0, 10], [2, 3], [4, 5], [6, 7]] needs 2 rooms: the long one, and one shared by the short ones.
    • Unordered input. [[7, 10], [2, 4]] needs 1 room. The sort handles any order of the input.
    • Forgetting the comparator. The default text ordering gives wrong event order, and so a wrong maximum.
    • Returning inside the loop. The maximum is known only after every event has been seen.

    Testing

    • [[5, 10], [0, 30], [15, 20]] gives 2.
    • [[1, 2], [2, 3]] gives 1.
    • [[1, 3], [2, 4]] gives 2.
    • [[1, 5], [1, 5], [1, 5]] gives 3.
    • [] gives 0.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free