LeetCode 2402. Meeting Rooms III の解き方メモ

LeetCode 2402. Meeting Rooms III の解き方メモです。それほど難しい問題ではないはずですが、問題の把握にてこずったので、考え方を共有しておきたいと思います。

問題の内容はおおよそ以下の通りです。

• N個の会議室とM個の会議予定が与えられる
• ルールにしたがって、会議室予約を行う
• すべての会議室予約が完了したとき、もっとも利用数の多い会議室の番号を求める。そのような会議室が複数ある場合は、もっとも番号が若いものを答えとする

把握に苦労したのが、会議室予約のルール。問題文がややわかりずらい気もするのですが、まとめるとおおよそ以下の通りになります。

• 会議室予約は開始予定時刻の昇順で処理する
• 空室がある場合は、その部屋を使う。空室が複数ある場合は、番号がもっとも若いものを使う
• 空室がない場合は、一番最初に空室になる部屋を使う。そのような部屋が複数ある場合は、番号がもっとも若いものを使う
  • 空室ができるまで待って、それから会議を始めるイメージ。そのため、会議開始時刻が遅くなっても、もともとの会議予定時間はそのままにする必要がある
  • 例. [8, 12)という会議予定について、時刻8の時点で空室がなく、時刻10になって初めて空室ができたとする。このとき、この会議は[10, 14)の時間で開催される

これをそのまま実装すればよいです。計算量は$O(M \log M + N \times M)$。$M \log M$はM個の会議予定を最初にソートする分ですね。$N \times M$は「空室があるかないかを探す・一番最初に空室になる部屋を探す」部分で、ここがボトルネックになりそうですが、$N \leqq 10^2, M \leqq 10^5 \Rightarrow N \times M \leqq 10^7$と制約が小さいため、すくなくともRustのような高速な言語であれば問題ありません。

use std::cmp::Reverse;

impl Solution {
    pub fn most_booked(n: i32, meetings: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut meetings = meetings;
        meetings.sort_unstable_by_key(|meeting| meeting[0]);

        let mut reserves = vec![0i128; n];
        let mut counter = vec![0i128; n];

        for meeting in meetings {
            let s1 = meeting[0] as i128;
            let e1 = meeting[1] as i128;

            // 空室があれば、その部屋を使う。
            // 空室が複数ある場合は、番号がもっとも若いものを使う。
            if let Some(room) = (0..n).filter(|&i| reserves[i] <= s1).min() {
                reserves[room] = e1;
                counter[room] += 1;
            } else {
                // 空室がない場合は、一番最初に空室になる部屋を使う。
                // そのような部屋が複数ある場合は、番号がもっとも若いものを使う。
                let room = (0..n).min_by_key(|&i| (reserves[i], i)).unwrap();
                reserves[room] = reserves[room] + (e1-s1);
                counter[room] += 1;
            }
        }

        // 会議の使用回数が多い部屋を選択する。
        // そのような部屋が複数ある場合は、番号がもっとも若いものを使う。
        (0..n).max_by_key(|&i| (counter[i], Reverse(i))).unwrap() as i32
    }
}