Meeting Room Partitioning (Rust)
Topics: scheduling, intervals, sweep line, greedy
Problem
Given meetings as half-open ranges [start, end), find the minimum number of rooms needed so no
two meetings in the same room overlap — equal to the maximum number of meetings happening at once.
#[derive(Clone, Copy)]
pub struct Interval { pub start: i64, pub end: i64 } // half-open [start, end)
pub fn min_rooms(meetings: &[Interval]) -> usize;
- Return the peak count of simultaneously-running meetings.
- Intervals are half-open: a meeting ending at
t and one starting at t do not overlap and
may share a room.
- Input may be unsorted.
[0,30) [5,10) [15,20) → 2
[1,5) [2,6) [3,7) → 3
[1,2) [2,3) → 1 (touching, not overlapping)
Use a sweep: sort all start times and all end times separately, then walk them together. Each
start claims a room, each end releases one; the high-water mark is the answer. Comparing with <
naturally processes an end before a start at the same time, so touching meetings share a room.
Sign in to submit your solution.