LESSON 354 OF 414 · GREEDY

Meeting Rooms in Scala: O(n log n) with Sorted Events

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 accommodate 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

SCALA · GREEDY

Meeting Rooms in Scala, explained

Problem overview

The method meetingRooms receives intervals, an Array[Array[Int]] in which each inner array holds the start and end time of one meeting. It returns the smallest number of rooms that lets every meeting happen without anyone waiting. Each end time is greater than its start time, and meetings that only touch, such as [1, 2] and [2, 3], don't overlap.

For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meeting from 0 to 30 is in progress the whole time, so it needs its own room. The other two don't overlap each other, so they can share a second room.

The statement asks for O(n log n) time and O(n) extra space, where n is the number of meetings.

Approach: turn meetings into events and sweep through time

The number of rooms you need equals the largest number of meetings running at the same moment. Comparing every pair of meetings to find that would be quadratic. A sweep over time is faster.

Split every meeting into two events: a start, which adds one running meeting, and an end, which removes one. Sort the events by time and walk through them while keeping a counter of running meetings. The highest value the counter ever reaches is the answer. Sorting costs O(n log n), the walk costs O(n), and the list of events holds 2n entries, which is O(n) space.

Each event is a pair (time, type), with type 1 for a start and -1 for an end. Those two numbers are chosen so that updating the counter is a single addition: noOfMeetings += event(1).

Ties need care. If one meeting ends at time 10 and another starts at 10, the room is free in time for the new meeting, so the end must be processed before the start. Sorting by time and then by type puts -1 before 1, which does exactly that.

Step by step

Create the event list. A val holding an empty scala.collection.mutable.ArrayBuffer[Array[Int]]. Scala's default collections are immutable, so you need the mutable buffer to append. The val only fixes which buffer events refers to; the buffer itself can still grow.
Loop over the meetings with for (interval <- intervals).
Add the start event Array(interval(0), 1) with +=. Scala indexes arrays with parentheses, so interval(0) is the start time.
Add the end event Array(interval(1), -1) the same way.
Sort the events with sortWith. Its function receives two events and returns true when the first must come before the second: compare the types when the times are equal, and the times otherwise. sortWith returns a new buffer instead of sorting in place, so the result goes into sorted.
Declare the counters. Two vars, answer and noOfMeetings, both starting at 0. They change inside the next loop, so val would not work.
Loop over sorted, not over events, which is still in insertion order.
Update the running count by adding the event's type.
Keep the maximum with math.max(answer, noOfMeetings).
End with answer as the last expression. A Scala method returns the value of its last expression, so no return is needed.

The solution in Scala

class Solution {
    def meetingRooms(intervals: Array[Array[Int]]): Int = {
        val events = scala.collection.mutable.ArrayBuffer[Array[Int]]()
        for (interval <- intervals) {
            events += Array(interval(0), 1)
            events += Array(interval(1), -1)
        }

        val sorted = events.sortWith((a, b) => {
                if (a(0) == b(0)) a(1) < b(1)
                else a(0) < b(0)
        })

        var answer = 0
        var noOfMeetings = 0
        for (event <- sorted) {
            noOfMeetings += event(1)
            answer = math.max(answer, noOfMeetings)
        }

        answer
    }
}

The Scala details worth a closer look:

if is an expression. The body of the comparison function is an if/else whose value is a Boolean, and that value is what the function returns. There is no return and no ternary operator.
vars inside a for loop. A for (x <- xs) { ... } loop runs its body as a function for each element. Scala still lets that body assign to vars declared outside it, so answer and noOfMeetings work as you would expect.
sortWith is stable and not in place. The original events buffer keeps its order. With the buffer (3, 1), (1, 1), the sorted copy is (1, 1), (3, 1), and events still lists (3, 1) first.
Arrays as pairs. A two-element Array[Int] works as a pair here, but the compiler doesn't know it has two elements. Reading event(2) would compile and fail at run time.

Complexity

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

Space: O(n). The buffer holds 2n small arrays, and sortWith creates a second buffer of the same size.

Edge cases and common mistakes

Touching meetings. [[1, 2], [2, 3]] returns 1. At time 2 the end event comes first, so the counter drops to 0 before it goes up again.
Sorting by time only. This breaks the tie rule. For [[2, 3], [1, 2]], a comparison that looks only at a(0) < b(0) keeps the start of the first meeting ahead of the end of the second at time 2, and the count reaches 2 instead of 1.
No meetings. An empty array has no events, the loop never runs, and the method returns 0.
Identical meetings. Three copies of [0, 5] return 3, because all three starts are processed before any end.
Iterating over events. The unsorted buffer lists each meeting's start and end together, so the counter would never go above 1.
Using val for the counters. Scala reports an error on the first reassignment.

Testing

[[5, 10], [0, 30], [15, 20]] gives 2.
[[1, 2], [2, 3]] gives 1.
[[2, 3], [1, 2]] gives 1.
[[0, 5], [0, 5], [0, 5]] gives 3.
[] gives 0.

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

Start learning free