Fewest Rooms Needed for a Day of Sessions

Medium20–25 min

Topics

GreedyHeapSortingIntervals

Companies

AmazonGoogleMicrosoftFacebook

A conference has a list of sessions, each with a start and an end time. A session occupies its room from its start up to (not including) its end, so a room can host a session that begins at the moment the previous one finishes. Find the smallest number of rooms that lets every session run at its scheduled time.

Scanning a list of rooms for a free one works, but a min-heap of end times always hands over the room that frees up first in O(log n).

Test Case 1:

Input:sessions = [[9, 12], [1, 4], [3, 8], [4, 6], [7, 10], [11, 15]]

Output:2

Explanation:Sessions [1,4] and [3,8] overlap so they need two rooms; every later session can reuse whichever room has just become free, so a third room is never needed.

Test Case 2:

Input:sessions = [[1, 4], [4, 6]]

Output:1

Explanation:The second session starts exactly when the first ends, so one room is enough.

Test Case 3:

Input:sessions = [[2, 5], [2, 5], [2, 5], [2, 5]]

Output:4

Explanation:Four identical sessions all run at once and each needs its own room.

Constraints

◆1 ≤ sessions.length ≤ 12; each session is [start, end] with 0 ≤ start < end ≤ 40
◆A session occupies its room from start up to (not including) end, so a room can host a session that starts exactly when the previous one ends
◆Sessions may be assigned to any room. Return the fewest rooms that let every session run at its scheduled time

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Assign Sessions to Rooms by Scanning the Room List

Brute

Process the sessions in order of start time while keeping a list with the time each existing room becomes free. For each session, scan the list from the front for any room that is already free by the session's start; if found, put the session there (that room is now free at the session's end), otherwise open a new room. The answer is the number of rooms opened. It is correct, but each session may scan every room, so the cost grows with sessions × rooms.

TimeO(n log n + n · rooms)

SpaceO(rooms)

Java

Try it out

class Solution {
    public int fewestRooms(int[][] sessions) {
        int[][] byStart = sessions.clone();
        Arrays.sort(byStart, (a, b) -> a[0] - b[0]);
        List<Integer> roomFreeAt = new ArrayList<>();
        for (int[] session : byStart) {
            boolean placed = false;
            for (int r = 0; r < roomFreeAt.size(); r++) {
                if (roomFreeAt.get(r) <= session[0]) {
                    roomFreeAt.set(r, session[1]);
                    placed = true;
                    break;
                }
            }
            if (!placed) roomFreeAt.add(session[1]);
        }
        return roomFreeAt.size();
    }
}

Optimal — Min-Heap of Room End Times

Optimal

Sort the sessions by start time and keep a min-heap of the end times of the sessions currently holding a room, so the root is the room that frees up first. For each session: if the root's end time is at or before the session's start, that room has just become free — pop it (the session takes over that room); either way push the session's end time. The heap's size is the number of rooms in use, and since it only grows when no room is free, its final size is the fewest rooms needed. Finding the room that frees up first costs O(log n) instead of a scan.

TimeO(n log n)

SpaceO(n)