Find the minimum rooms needed for overlapping bookings
A recording studio rents out identical rooms. Before opening bookings for a day, the manager wants to know how many rooms must be available so that no two overlapping sessions end up in the same room.
Implement minRoomsNeeded(bookings). It returns the smallest number of rooms that can host every booking.
minRoomsNeeded(bookings) // => number
bookings is an array of [start, end] pairs of finite numbers (for example, minutes since midnight). It is not sorted.start is never greater than end.start up to, but not including, end. A booking that ends at 600 and one that starts at 600 can use the same room.start === end takes no time and needs no room.0 when no room is needed (for example, for an empty array).bookings or any of its pairs.minRoomsNeeded([[540, 600], [570, 630], [600, 660], [615, 645]]);
// => 3 (from 615 to 630, three sessions run at once)
minRoomsNeeded([[780, 840], [660, 720], [720, 780]]);
// => 1 (back-to-back sessions share one room)
minRoomsNeeded([[60, 300], [90, 120], [150, 180]]);
// => 2
minRoomsNeeded([[500, 500]]);
// => 0
minRoomsNeeded([]);
// => 0
A solution that compares every pair of bookings is O(n²). Aim for O(n log n).