Meeting Rooms 3

Problem

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.
2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
3. When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

Examples

Example 1:

Input: intervals =[[1,2],[4,5],[8,10]], rooms = 1, ask =[[2,3],[3,4]]
Output: [true,true]
Explanation:
For the ask of [2,3], we can arrange a meeting room room0.
The following is the meeting list of room0:
[[1,2], [2,3], [4,5], [8,10]]
For the ask of [3,4], we can arrange a meeting room room0.
The following is the meeting list of room0:
[[1,2], [3,4], [4,5], [8,10]]

Example 2:

Input: intervals =[[1,2],[4,5],[8,10]], rooms = 1, ask =[[4,5],[5,6]]
Output: [false,true]

Solution

Method 1 - Sorting and Tracking All Intervals

Intuition

We want to efficiently answer queries about whether a meeting can be scheduled in a room, given existing meetings. By tracking the number of rooms occupied at each time, we can quickly check if a new meeting can fit without exceeding the room limit.

Approach

1. Sort all meeting intervals by start time.
2. Use an array to track the number of rooms occupied at each time.
3. For each query interval, check if at any time in the interval the number of rooms occupied reaches the limit k.
4. Return a boolean array indicating if each query can be scheduled.

Code

C++

vector<bool> meetingRoom(vector<vector<int>>& calendar, int k, vector<vector<int>>& query) {
    sort(calendar.begin(), calendar.end());
    int n = 0;
    for (auto& interval : calendar) n = max(n, interval[1]);
    vector<int> rooms(n+1, 0);
    for (auto& interval : calendar) {
        for (int t = interval[0]; t < interval[1]; ++t) rooms[t]++;
    }
    vector<bool> result;
    for (auto& q : query) {
        bool canSchedule = true;
        for (int t = q[0]; t < q[1]; ++t) {
            if (rooms[t] >= k) {
                canSchedule = false;
                break;
            }
        }
        result.push_back(canSchedule);
    }
    return result;
}

Go

func meetingRoom(calendar [][]int, k int, query [][]int) []bool {
    sort.Slice(calendar, func(i, j int) bool { return calendar[i][0] < calendar[j][0] })
    n := 0
    for _, interval := range calendar {
        if interval[1] > n {
            n = interval[1]
        }
    }
    rooms := make([]int, n+1)
    for _, interval := range calendar {
        for t := interval[0]; t < interval[1]; t++ {
            rooms[t]++
        }
    }
    result := make([]bool, len(query))
    for i, q := range query {
        canSchedule := true
        for t := q[0]; t < q[1]; t++ {
            if rooms[t] >= k {
                canSchedule = false
                break
            }
        }
        result[i] = canSchedule
    }
    return result
}

Java

class Solution {
    public boolean[] meetingRoom(int[][] calendar, int k, int[][] query) {
        Arrays.sort(calendar, Comparator.comparingInt(a -> a[0]));
        int n = 0;
        for (int[] interval : calendar) n = Math.max(n, interval[1]);
        int[] rooms = new int[n+1];
        for (int[] interval : calendar) {
            for (int t = interval[0]; t < interval[1]; t++) rooms[t]++;
        }
        boolean[] result = new boolean[query.length];
        for (int i = 0; i < query.length; i++) {
            int[] q = query[i];
            boolean canSchedule = true;
            for (int t = q[0]; t < q[1]; t++) {
                if (rooms[t] >= k) {
                    canSchedule = false;
                    break;
                }
            }
            result[i] = canSchedule;
        }
        return result;
    }
}

Kotlin

class Solution {
    fun meetingRoom(calendar: Array<IntArray>, k: Int, query: Array<IntArray>): BooleanArray {
        calendar.sortBy { it[0] }
        var n = 0
        for (interval in calendar) n = maxOf(n, interval[1])
        val rooms = IntArray(n+1)
        for (interval in calendar) {
            for (t in interval[0] until interval[1]) rooms[t]++
        }
        val result = BooleanArray(query.size)
        for (i in query.indices) {
            val q = query[i]
            var canSchedule = true
            for (t in q[0] until q[1]) {
                if (rooms[t] >= k) {
                    canSchedule = false
                    break
                }
            }
            result[i] = canSchedule
        }
        return result
    }
}

Python

def meetingRoom(calendar: list[list[int]], k: int, query: list[list[int]]) -> list[bool]:
    calendar.sort()
    n = max(interval[1] for interval in calendar)
    rooms = [0] * (n+1)
    for interval in calendar:
        for t in range(interval[0], interval[1]):
            rooms[t] += 1
    result = []
    for q in query:
        can_schedule = True
        for t in range(q[0], q[1]):
            if rooms[t] >= k:
                can_schedule = False
                break
        result.append(can_schedule)
    return result

Rust

pub fn meeting_room(calendar: Vec<Vec<i32>>, k: i32, query: Vec<Vec<i32>>) -> Vec<bool> {
    let mut calendar = calendar;
    calendar.sort_by_key(|x| x[0]);
    let n = calendar.iter().map(|x| x[1]).max().unwrap_or(0);
    let mut rooms = vec![0; (n+1) as usize];
    for interval in &calendar {
        for t in interval[0]..interval[1] {
            rooms[t as usize] += 1;
        }
    }
    let mut result = Vec::new();
    for q in &query {
        let mut can_schedule = true;
        for t in q[0]..q[1] {
            if rooms[t as usize] >= k {
                can_schedule = false;
                break;
            }
        }
        result.push(can_schedule);
    }
    result
}

TypeScript

function meetingRoom(calendar: number[][], k: number, query: number[][]): boolean[] {
    calendar.sort((a, b) => a[0] - b[0]);
    let n = 0;
    for (const interval of calendar) n = Math.max(n, interval[1]);
    const rooms = new Array(n+1).fill(0);
    for (const interval of calendar) {
        for (let t = interval[0]; t < interval[1]; t++) rooms[t]++;
    }
    const result: boolean[] = [];
    for (const q of query) {
        let canSchedule = true;
        for (let t = q[0]; t < q[1]; t++) {
            if (rooms[t] >= k) {
                canSchedule = false;
                break;
            }
        }
        result.push(canSchedule);
    }
    return result;
}

Complexity

• ⏰ Time complexity: O(N + Q * D), where N is the total time range, Q is the number of queries, and D is the duration of each query.
• 🧺 Space complexity: O(N) for the rooms array.