LESSON 329 OF 347 · GREEDY

Meeting Rooms in C#: Sweeping Start and End Events in 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:

You may assume the interval's end point is always greater than its start point.
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

Guided

Ctrl + Enter to check

Meeting Rooms in C#, explained

Problem overview

The method MeetingRooms(int[,] intervals) receives meetings as rows of a two-dimensional array: column 0 is the start time and column 1 the end time. It returns the minimum number of rooms needed so that every meeting has a room during its whole time. Each end is greater than its start, and meetings that merely touch, like [1, 2] and [2, 3], can share a room.

For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meeting from 0 to 30 occupies one room the whole time. The meetings from 5 to 10 and from 15 to 20 never overlap each other, so they can share the second room.

Approach: count meetings in progress

The number of rooms you need equals the largest number of meetings running at the same moment. To find that peak, turn each meeting into two events: a start at its start time that adds one running meeting, and an end at its end time that removes one. Sort the events by time and sweep through them, keeping a running count. The highest value of the count is the answer.

Ties need care. When one meeting ends at the same moment another begins, the room is free before the new meeting needs it, so the end event must be handled first. Giving ends the type -1 and starts the type 1, and sorting by type when the times are equal, puts ends first automatically.

Checking every pair of meetings for conflicts, or every moment in time, is slower or depends on the size of the time values. Sorting the 2n events costs only O(n log n).

Step by step

Create the event list. A List<int[]>, where each event is an int[] pair of time and type. A List grows as you add to it, which suits this because you do not know the size up front.
Loop over the meetings. The input is a 2D array, so the number of rows is intervals.GetLength(0). On a 2D array, Length would count every cell and give twice as many.
Add a start event new int[]{intervals[i, 0], 1}.
Add an end event new int[]{intervals[i, 1], -1}.
Sort the list with a comparison lambda. If the times are equal, compare the types, so -1 comes before 1. Otherwise compare the times. Arrays have no natural ordering in C#, so the comparison must be supplied.
Declare the counters answer and noOfMeetings, both 0. The second counts meetings in progress, and the first remembers the largest value seen.
Sweep with foreach. Name the loop variable ev, because event is a C# keyword.
Apply the event. Add its type to noOfMeetings. Types of 1 and -1 turn that into a single addition.
Track the peak with answer = Math.Max(answer, noOfMeetings).
Return answer after the loop. The maximum is only known once all events are processed.

The solution in C#

class Solution {
    public int MeetingRooms(int[,] intervals) {
        List<int[]> events = new List<int[]>();
        for (int i = 0; i < intervals.GetLength(0); i++) {
            events.Add(new int[]{intervals[i, 0], 1});
            events.Add(new int[]{intervals[i, 1], -1});
        }

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

        int answer = 0, noOfMeetings = 0;
        foreach (int[] ev in events) {
            noOfMeetings += ev[1];
            answer = Math.Max(answer, noOfMeetings);
        }

        return answer;
    }
}

On the example, the sorted events are: (0, start), (5, start), (10, end), (15, start), (20, end), (30, end). The running count goes 1, 2, 1, 2, 1, 0, so the peak is 2.

C# details:

List<T>.Sort with a lambda. The lambda is a Comparison<int[]>. It returns a negative number if a goes first, a positive one if b does, and 0 for equal events.
Subtracting to compare. The subtraction is fine for ordinary times. If times could reach the extremes of int, the difference could overflow and flip its sign, and a[0].CompareTo(b[0]) would be the safe choice.
GetLength(0) versus Length. For a rectangular array, the first counts rows and the second counts all elements.
Several variables in one declaration. int answer = 0, noOfMeetings = 0; makes two separate int variables.

Complexity

Time: O(n log n). Building the events is O(n), sorting 2n events is O(n log n), and the sweep is O(n).

Space: O(n). The list holds 2n small arrays.

Edge cases and common mistakes

Touching meetings. [[1, 2], [2, 3]] needs 1 room. With the tie rule reversed (starts before ends at equal times), the count would reach 2 and the answer would be wrong.
Identical meetings. [[1, 3], [1, 3], [2, 4]] needs 3 rooms: all three are running at time 2.
No meetings. With zero rows there are no events, and the method returns 0.
Returning the final count. After all events the count is always 0. The answer is the peak, so it has to be tracked on every event.
Using event as a variable name. It is a keyword and will not compile as a plain identifier.
Sorting only by time. A tie between an end and a start could then fall either way, because a sort is free to order equal items however it likes.

Testing

[[5, 10], [0, 30], [15, 20]] gives 2.
[[1, 2], [2, 3]] gives 1.
[[1, 3], [1, 3], [2, 4]] gives 3.
An empty list of meetings gives 0.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free