Start learning free

LESSON 330 OF 348 · GREEDY

Meeting Rooms II in Kotlin: O(n log n) Sweep Over Start and End 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 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

    KOTLIN · GREEDY

    Meeting Rooms in Kotlin, explained

    Problem overview

    The function meetingRooms(intervals) receives an Array<IntArray> in which each pair is a meeting's [start, end] time. It returns the minimum number of rooms needed so that all meetings can take place. Two meetings that only touch, such as [1, 2] and [2, 3], can share a room. The statement asks for O(n log n) time and O(n) extra space.

    For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meeting from 5 to 10 and the one from 15 to 20 can use one room, one after the other, while the meeting from 0 to 30 runs across both and needs a second room.

    Approach: count the meetings running at each moment

    The number of rooms you need equals the largest number of meetings in progress at the same moment. You could test every moment against every meeting, but there is a cheaper way: sweep through time and keep a running count.

    Turn every meeting into two events: one at its start time that adds 1 to the count and one at its end time that subtracts 1. Sort all events by time. Walk through them in order and update the count, and the maximum value the count ever reaches is the answer. With n meetings there are 2n events, and the sort costs O(n log n).

    One detail needs care: events at the same time. A meeting that ends at time 2 and another that starts at time 2 don't overlap, so the end must be processed first. If the start came first, the count would briefly count both meetings and report one room too many. That is why the pair is (time, type) with type -1 for an end and 1 for a start, and why the sort puts -1 before 1 when the times are equal.

    On the example, the events in order are: (0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1). The running count is 1, 2, 1, 2, 1, 0, and its maximum is 2.

    Step by step

    1. Create the list of events. events is a val holding an empty ArrayList<IntArray>. Each event is a two-element IntArray: time, then type.
    2. Loop over the meetings. Name each one interval.
    3. Add the start event, intArrayOf(interval[0], 1).
    4. Add the end event, intArrayOf(interval[1], -1).
    5. Sort the events with sortWith and a Comparator. An IntArray has no natural order, so the comparator is needed. It compares the types when the times are equal and the times otherwise.
    6. Declare answer and noOfMeetings, both starting at 0. The second counts meetings in progress, and the first remembers the largest count seen.
    7. Loop over the sorted events.
    8. Add the event's type to noOfMeetings. The +1 and -1 encoding turns "a meeting started" and "a meeting ended" into a single addition.
    9. Update answer to maxOf(answer, noOfMeetings).
    10. Return answer after the loop. The maximum is only known once every event has been processed.

    The solution in Kotlin

    class Solution {
    fun meetingRooms(intervals: Array<IntArray>): Int {
        val events = ArrayList<IntArray>()
        for (interval in intervals) {
            events.add(intArrayOf(interval[0], 1))
            events.add(intArrayOf(interval[1], -1))
        }

        events.sortWith(Comparator { a, b ->
                if (a[0] == b[0]) a[1] - b[1] else a[0] - b[0]
        })

        var answer = 0
        var noOfMeetings = 0
        for (event in events) {
            noOfMeetings += event[1]
            answer = maxOf(answer, noOfMeetings)
        }

        return answer
    }
}

    The Kotlin details worth a closer look:

    • if is an expression. The lambda body if (a[0] == b[0]) a[1] - b[1] else a[0] - b[0] produces a value, and the lambda returns its last expression. No return is needed inside it.
    • Comparator results. A comparator returns a negative number when a sorts first, a positive one when b does, and 0 for a tie. With equal times, a[1] - b[1] is negative when a is an end (-1) and b is a start (1), so ends come first.
    • Subtraction can overflow. a[0] - b[0] works for realistic times, but Int arithmetic wraps: 2000000000 - (-2000000000) evaluates to -294967296, which has the wrong sign. For times that could be that far apart, compare with a[0].compareTo(b[0]) instead.
    • ArrayList<IntArray> and val. val events fixes the reference, but the list can still grow with add.
    • intArrayOf. It builds an IntArray from the values you pass it.
    • for (x in collection). It loops directly over the elements, so there is no index to get wrong.

    Complexity

    Time: O(n log n). Building the 2n events is O(n), sorting them 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]] returns 1. If starts were processed before ends at the same time, the result would be 2.
    • Fully nested or overlapping meetings. [[1, 5], [2, 6], [3, 7]] returns 3: at time 3 all three are running.
    • Separate meetings. [[1, 2], [3, 4]] returns 1.
    • A single meeting and no meetings. [[1, 2]] returns 1, and an empty array returns 0, since the loop over events does nothing.
    • Taking the final count instead of the maximum. After every event the count is back at 0, so returning noOfMeetings would always give 0. The answer is the largest value along the way.
    • Returning inside the loop. The maximum can occur at any event, so the return belongs after the loop.
    • Sorting by time only. That leaves the order of equal-time events up to the sort and can produce a room count that is too high for touching meetings.

    Testing

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