1. Insert Interval
Medium · LC 57
Given sorted non-overlapping intervals and one new interval, insert and merge it so the result stays sorted and non-overlapping. Process in three phases: copy intervals ending before the new one starts, then absorb every overlapping interval by taking min start and max end, then copy the rest. The pitfall is the overlap test: an interval overlaps while its start is at most the merged end, and the merged interval is appended exactly once.
def insert_interval(
intervals: list[list[int]], new_interval: list[int]
// LC 57. The input is already sorted and non-overlapping, so insertion runs in
// three phases: copy every interval that ends before the new one starts,
// absorb every interval that overlaps by taking the min start and max end,
// then copy the rest untouched. The pitfall is the overlap test -- an interval
// overlaps while its start is at most the merged end (touching counts) -- and
// the merged interval is appended exactly once, between phases two and three.
vector<vector<int>> insertInterval(vector<vector<int>> intervals, vector<int> newInterval) {
int n = static_cast<int>(intervals.size());
vector<vector<int>> result;
int i = 0;
while (i < n && intervals[i][1] < newInterval[0]) // phase 1: strictly before
result.push_back(intervals[i++]);
while (i < n && intervals[i][0] <= newInterval[1]) { // phase 2: absorb overlaps
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
++i;
}
result.push_back(newInterval);
while (i < n) result.push_back(intervals[i++]); // phase 3: strictly after
return result;
}
/// LC 57. Three phases over the already-sorted list: copy intervals ending
/// before the new one starts, absorb every overlapping interval by taking min
/// start and max end, then copy the rest. The overlap test is start <= merged
/// end (closed intervals touch-merge), and the merged interval is pushed
/// exactly once between the phases.
pub fn insert_interval(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
let (mut start, mut end) = (new_interval[0], new_interval[1]);
let mut result: Vec<Vec<i32>> = Vec::with_capacity(intervals.len() + 1);
let mut i = 0;
while i < intervals.len() && intervals[i][1] < start {
result.push(intervals[i].clone()); // phase 1: entirely before
i += 1;
}
while i < intervals.len() && intervals[i][0] <= end {
start = start.min(intervals[i][0]); // phase 2: absorb overlaps
end = end.max(intervals[i][1]);
i += 1;
}
result.push(vec![start, end]);
result.extend_from_slice(&intervals[i..]); // phase 3: entirely after
result
}
/** LC 57. Three phases: copy intervals ending before, absorb overlaps with min/max, copy the rest. */
export function insertInterval(intervals: number[][], newInterval: number[]): number[][] {
const result: number[][] = [];
let [start, end] = newInterval;
let i = 0;
while (i < intervals.length && intervals[i][1] < start) result.push(intervals[i++]); // strictly before
while (i < intervals.length && intervals[i][0] <= end) {
// overlaps while its start is at most the merged end; absorb by widening both edges
start = Math.min(start, intervals[i][0]);
end = Math.max(end, intervals[i][1]);
i++;
}
result.push([start, end]); // the merged interval is appended exactly once
while (i < intervals.length) result.push(intervals[i++]); // strictly after
return result;
}
// LC 57. Three phases over the already-sorted input: copy what ends before
// the new interval, absorb every overlap into min-start/max-end, copy the rest.
func insertInterval(intervals [][]int, newInterval []int) [][]int {
start, end := newInterval[0], newInterval[1]
n := len(intervals)
result := [][]int{}
i := 0
for i < n && intervals[i][1] < start { // phase 1: strictly before
result = append(result, intervals[i])
i++
}
for i < n && intervals[i][0] <= end { // phase 2: absorb overlaps (touching counts)
if intervals[i][0] < start {
start = intervals[i][0]
}
if intervals[i][1] > end {
end = intervals[i][1]
}
i++
}
result = append(result, []int{start, end}) // the absorbed interval, exactly once
for i < n { // phase 3: strictly after
result = append(result, intervals[i])
i++
}
return result
}
// LC 57. Three phases over the already-sorted input: copy intervals ending
// before the new one, absorb every overlap into min start / max end (touching
// counts, hence <=), append the merged interval once, then copy the rest.
func insertInterval(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
var newStart = newInterval[0]
var newEnd = newInterval[1]
var merged: [[Int]] = []
var i = 0
let n = intervals.count
while i < n && intervals[i][1] < newStart { // phase 1: strictly before
merged.append(intervals[i])
i += 1
}
while i < n && intervals[i][0] <= newEnd { // phase 2: absorb overlaps
newStart = min(newStart, intervals[i][0])
newEnd = max(newEnd, intervals[i][1])
i += 1
}
merged.append([newStart, newEnd]) // the absorbed interval, exactly once
while i < n { // phase 3: strictly after
merged.append(intervals[i])
i += 1
}
return merged
}
2. Merge Intervals
Medium · LC 56
Given an unsorted list of intervals, merge all overlapping ones and return the resulting non-overlapping intervals. Sort by start, then sweep while keeping an active interval, extending its end with max whenever the next start falls at or before the active end, and emitting the active interval otherwise. The detail worth remembering is that extension must use max of the ends, since a later interval can be fully contained inside the active one.
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
"""LC 56. Merge Intervals.
Sort by start, then sweep keeping one active interval at the tail
of the output: when the next start falls at or before the active
end, extend; otherwise emit a fresh interval. Extension must take
max of the ends, because a later interval can sit entirely INSIDE
the active one. O(n log n) time, O(n) space.
"""
ordered = sorted(intervals)
merged = [list(ordered[0])]
for start, end in ordered[1:]:
active = merged[-1]
if start <= active[1]:
active[1] = max(active[1], end) # max: this one may be contained
else:
merged.append([start, end])
return merged
// LC 56. Sort by start, then sweep keeping one active interval: when the next
// start falls at or before the active end the two overlap, so extend the end;
// otherwise emit the active interval and start a new one. The detail worth
// remembering is that extension must take the MAX of the ends, because a later
// interval can be fully contained inside the active one.
vector<vector<int>> mergeIntervals(vector<vector<int>> intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (const vector<int>& iv : intervals) {
if (merged.empty() || iv[0] > merged.back()[1])
merged.push_back(iv); // gap: start a new active interval
else
merged.back()[1] = max(merged.back()[1], iv[1]); // contained intervals can't shrink it
}
return merged;
}
/// LC 56. Sort by start and sweep with an active interval: extend its end
/// with MAX while the next start falls at or before it, emit otherwise. The
/// max is the detail people drop -- a later interval can sit entirely inside
/// the active one, and plain assignment would shrink it.
pub fn merge_intervals(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
intervals.sort_unstable_by_key(|iv| iv[0]);
let mut result: Vec<Vec<i32>> = Vec::new();
for iv in intervals {
match result.last_mut() {
Some(active) if iv[0] <= active[1] => active[1] = active[1].max(iv[1]),
_ => result.push(iv),
}
}
result
}
/** LC 56. Sort by start, sweep an active interval, extending its end with max before emitting. */
export function mergeIntervals(intervals: number[][]): number[][] {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
const merged: number[][] = [];
for (const [start, end] of sorted) {
if (merged.length > 0 && start <= merged[merged.length - 1][1]) {
// max, not assignment: a later interval can sit fully inside the active one
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], end);
} else {
merged.push([start, end]);
}
}
return merged;
}
// LC 56. Sort by start and sweep one active interval: extend its end with a
// MAX (later intervals may be fully contained), or emit and start anew on a gap.
func mergeIntervals(intervals [][]int) [][]int {
ordered := append([][]int(nil), intervals...)
sort.Slice(ordered, func(a, b int) bool {
if ordered[a][0] != ordered[b][0] {
return ordered[a][0] < ordered[b][0]
}
return ordered[a][1] < ordered[b][1]
})
merged := [][]int{}
for _, iv := range ordered {
if len(merged) == 0 || iv[0] > merged[len(merged)-1][1] {
merged = append(merged, []int{iv[0], iv[1]}) // gap: start a new active interval
} else if iv[1] > merged[len(merged)-1][1] {
merged[len(merged)-1][1] = iv[1] // contained intervals can't shrink it
}
}
return merged
}
// LC 56. Sort by start, then sweep one active interval at the output's tail:
// overlap extends the end with MAX (a later interval can sit entirely
// inside), a gap starts a fresh interval.
func mergeIntervals(_ intervals: [[Int]]) -> [[Int]] {
let ordered = intervals.sorted { ($0[0], $0[1]) < ($1[0], $1[1]) }
var merged: [[Int]] = []
for iv in ordered {
if merged.isEmpty || iv[0] > merged[merged.count - 1][1] {
merged.append(iv) // gap: start a new active interval
} else {
merged[merged.count - 1][1] = max(merged[merged.count - 1][1], iv[1])
}
}
return merged
}
3. Non Overlapping Intervals
Medium · LC 435
Given a list of intervals, return the minimum number to remove so the remaining intervals do not overlap. Sort by end time, sweep while keeping the interval with the earliest end, count a removal whenever the next interval starts before the current kept end, and otherwise advance the kept end. The exchange argument is the heart: keeping the earliest-ending interval never hurts, because it leaves the most room for everything after, giving O(n log n).
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
"""LC 435. Non-overlapping Intervals.
Minimum removals = total minus the most intervals that can coexist,
and the classic greedy finds that maximum: sort by END time, sweep
keeping the earliest-ending interval, and remove (count) anything
that starts before the kept end. Touching at an endpoint is fine,
so only a strict < start conflicts. O(n log n) time, O(n) space
for the sort.
"""
removed = 0
earliest_finish = float("-inf") # end of the last interval we kept
for start, end in sorted(intervals, key=lambda iv: iv[1]): # sort by END
if start < earliest_finish:
# exchange argument: the kept interval ends no later than this
# one, so dropping THIS one never costs a better future choice
removed += 1
else:
earliest_finish = end
return removed
// LC 435. Sort by END time and sweep, always keeping the interval with the
// earliest end: count a removal whenever the next interval starts before the
// kept end, and otherwise advance the kept end. The exchange argument is the
// heart -- keeping the earliest-ending interval never hurts because it leaves
// the most room for everything after it. Touching at an endpoint is not an
// overlap, hence the strict <. O(n log n).
int eraseOverlapIntervals(vector<vector<int>> intervals) {
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
int removed = 0;
long long keptEnd = LLONG_MIN; // end of the last interval kept
for (const vector<int>& iv : intervals) {
if (iv[0] < keptEnd)
++removed; // overlaps the kept one; drop the later-ending interval
else
keptEnd = iv[1];
}
return removed;
}
/// LC 435. Sort by END time and greedily keep the earliest-ending interval,
/// counting a removal whenever the next interval starts before the kept end.
/// The exchange argument: the earliest finisher leaves the most room for
/// everything after it, so keeping it is never wrong. Touching endpoints do
/// not overlap.
pub fn erase_overlap_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
intervals.sort_unstable_by_key(|iv| iv[1]);
let mut removed = 0;
let mut kept_end = i32::MIN;
for iv in &intervals {
if iv[0] < kept_end {
removed += 1; // overlaps the kept interval: drop this later finisher
} else {
kept_end = iv[1];
}
}
removed
}
/** LC 435. Sort by END; keeping the earliest-ending interval leaves the most room, count the rest. */
export function eraseOverlapIntervals(intervals: number[][]): number {
const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
let removed = 0;
let keptEnd = -Infinity; // end of the last interval kept
for (const [start, end] of sorted) {
if (start < keptEnd) removed++; // overlaps the kept one: dropping this is never worse
else keptEnd = end;
}
return removed;
}
// LC 435. Sort by END and always keep the earliest finisher; count a removal
// whenever the next start lands strictly before the kept end (exchange argument).
func eraseOverlapIntervals(intervals [][]int) int {
ordered := append([][]int(nil), intervals...)
sort.Slice(ordered, func(a, b int) bool { return ordered[a][1] < ordered[b][1] })
removed := 0
keptEnd := math.MinInt // end of the last interval kept
for _, iv := range ordered {
if iv[0] < keptEnd {
removed++ // overlaps the kept one; drop the later-ending interval
} else {
keptEnd = iv[1]
}
}
return removed
}
// LC 435. Sort by END and always keep the earliest finisher: count a removal
// whenever the next start lands before the kept end -- the exchange argument
// says keeping the earliest end leaves the most room. Touching is fine.
func eraseOverlapIntervals(_ intervals: [[Int]]) -> Int {
let byEnd = intervals.sorted { $0[1] < $1[1] }
var removed = 0
var keptEnd = Int.min // end of the last interval kept
for iv in byEnd {
if iv[0] < keptEnd {
removed += 1 // overlaps the kept one; drop the later-ending interval
} else {
keptEnd = iv[1]
}
}
return removed
}
4. Meeting Rooms
Easy · LC 252
Given a list of meeting time intervals, determine whether one person can attend them all, meaning no two intervals overlap. Sort the intervals by start time and scan adjacent pairs, returning false the moment a meeting starts before the previous one ends. Sorting reduces the all-pairs overlap question to neighbor checks only, and intervals that touch exactly at an endpoint count as non-overlapping.
def can_attend_meetings(intervals: list[list[int]]) -> bool:
"""LC 252. Meeting Rooms.
One person can attend everything iff no two meetings overlap.
Sorting by start reduces the all-pairs question to adjacent pairs:
any overlap anywhere forces an overlap between some sorted
neighbors. Meetings that touch at an endpoint do NOT conflict, so
only a start strictly before the previous end fails. O(n log n)
time, O(n) space for the sort.
"""
ordered = sorted(intervals)
for (_, prev_end), (next_start, _) in zip(ordered, ordered[1:]):
if next_start < prev_end: # strict: back-to-back meetings are fine
return False
return True
// LC 252. One person can attend everything iff no two meetings overlap.
// Sorting by start time reduces the all-pairs question to adjacent pairs only:
// return false the moment a meeting starts before the previous one ends.
// Intervals that touch exactly at an endpoint count as non-overlapping, so the
// comparison is strict.
bool canAttendMeetings(vector<vector<int>> intervals) {
sort(intervals.begin(), intervals.end());
for (int i = 1; i < static_cast<int>(intervals.size()); ++i)
if (intervals[i][0] < intervals[i - 1][1]) return false;
return true;
}
/// LC 252. Sort by start time; one person can attend everything iff every
/// adjacent pair is disjoint, since sorting reduces the all-pairs overlap
/// question to neighbor checks. A meeting starting exactly when the previous
/// ends is fine.
pub fn can_attend_meetings(mut intervals: Vec<Vec<i32>>) -> bool {
intervals.sort_unstable_by_key(|iv| iv[0]);
intervals.windows(2).all(|pair| pair[0][1] <= pair[1][0])
}
/** LC 252. Sort by start; sorting reduces all-pairs overlap to adjacent checks only. */
export function canAttendMeetings(intervals: number[][]): boolean {
const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
for (let i = 1; i < sorted.length; i++) {
if (sorted[i][0] < sorted[i - 1][1]) return false; // touching endpoints do not overlap
}
return true;
}
// LC 252. Sort by start so only sorted neighbors can clash; touching at an
// endpoint is fine, so fail only on a start strictly before the previous end.
func canAttendMeetings(intervals [][]int) bool {
ordered := append([][]int(nil), intervals...)
sort.Slice(ordered, func(a, b int) bool {
if ordered[a][0] != ordered[b][0] {
return ordered[a][0] < ordered[b][0]
}
return ordered[a][1] < ordered[b][1]
})
for i := 1; i < len(ordered); i++ {
if ordered[i][0] < ordered[i-1][1] {
return false
}
}
return true
}
// LC 252. Sort by start so only neighbors can clash: fail the moment a
// meeting starts strictly before the previous one ends (touching is fine).
func canAttendMeetings(_ intervals: [[Int]]) -> Bool {
let ordered = intervals.sorted { ($0[0], $0[1]) < ($1[0], $1[1]) }
for i in stride(from: 1, to: ordered.count, by: 1)
where ordered[i][0] < ordered[i - 1][1] {
return false
}
return true
}
5. Meeting Rooms II
Medium · LC 253
Given meeting time intervals, return the minimum number of conference rooms needed to hold them all. Sort the start times and end times separately, then sweep both arrays with two pointers, incrementing the room count when the next start is before the earliest unfinished end and otherwise advancing the end pointer. The answer is the peak count of simultaneous meetings, and the sweep works because only event ordering matters, not which meeting owns which time.
def min_meeting_rooms(intervals: list[list[int]]) -> int:
"""LC 253. Meeting Rooms II.
The answer is the peak number of simultaneous meetings. Sort the
start times and end times SEPARATELY and sweep with two pointers:
a start before the earliest unfinished end opens one more room, and
otherwise the end pointer advances. Decoupling the endpoints is
legal because only event ordering matters, never which meeting owns
which time. O(n log n) time, O(n) space.
"""
starts = sorted(start for start, _ in intervals)
ends = sorted(end for _, end in intervals)
rooms_in_use, peak, end_i = 0, 0, 0
for start in starts:
if start < ends[end_i]:
rooms_in_use += 1 # overlaps the earliest unfinished meeting
else:
# the earliest end is <= this start, so that meeting already
# finished and its room is free -- this meeting reuses it
end_i += 1
peak = max(peak, rooms_in_use)
return peak
// LC 253. Sort the start times and end times into two separate arrays and
// sweep with two pointers: each start before the earliest unfinished end needs
// a fresh room, otherwise that earliest meeting has ended and its room is
// reused (advance the end pointer). Decoupling starts from ends is legal
// because only the ordering of events matters, not which meeting owns which
// room; end == start frees the room in time, hence the strict <.
int minMeetingRooms(vector<vector<int>> intervals) {
int n = static_cast<int>(intervals.size());
vector<int> starts(n), ends(n);
for (int i = 0; i < n; ++i) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, e = 0;
for (int s = 0; s < n; ++s) {
if (starts[s] < ends[e])
++rooms; // meeting starts before the earliest one finishes
else
++e; // reuse the room that just freed up
}
return rooms;
}
/// LC 253. Sort starts and ends into two separate Vecs and sweep with two
/// pointers: a start before the earliest unfinished end opens a room, and
/// otherwise a meeting has ended, closing one. The answer is the PEAK of the
/// running count, not its final value, and only event ordering matters -- no
/// one cares which meeting owns which time.
pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
let mut starts: Vec<i32> = intervals.iter().map(|iv| iv[0]).collect();
let mut ends: Vec<i32> = intervals.iter().map(|iv| iv[1]).collect();
starts.sort_unstable();
ends.sort_unstable();
let (mut s, mut e) = (0, 0);
let (mut count, mut peak) = (0, 0);
while s < starts.len() {
if starts[s] < ends[e] {
s += 1;
count += 1;
peak = peak.max(count);
} else {
e += 1; // strict <: a meeting ending exactly now frees its room
count -= 1;
}
}
peak
}
/** LC 253. Sort starts and ends separately; two pointers count the peak of simultaneous meetings. */
export function minMeetingRooms(intervals: number[][]): number {
const starts = intervals.map((interval) => interval[0]).sort((a, b) => a - b);
const ends = intervals.map((interval) => interval[1]).sort((a, b) => a - b);
let rooms = 0;
let endPtr = 0; // earliest unfinished end
for (const start of starts) {
if (start < ends[endPtr]) rooms++; // a meeting is still running: a new room opens
else endPtr++; // end <= start frees a room that this meeting reuses
}
return rooms; // rooms never decrements, so it finishes at the peak
}
// LC 253. Sort starts and ends separately and sweep two pointers: a start
// before the earliest unfinished end opens a room, otherwise one is reused.
func minMeetingRooms(intervals [][]int) int {
n := len(intervals)
starts := make([]int, n)
ends := make([]int, n)
for i, iv := range intervals {
starts[i], ends[i] = iv[0], iv[1]
}
sort.Ints(starts)
sort.Ints(ends)
rooms, e := 0, 0
for s := 0; s < n; s++ {
if starts[s] < ends[e] {
rooms++ // meeting starts before the earliest one finishes
} else {
e++ // reuse the room that just freed up
}
}
return rooms
}
// LC 253. Sort starts and ends SEPARATELY and sweep two pointers: a start
// before the earliest unfinished end opens a room, otherwise that meeting is
// over and its room is reused. Only event ordering matters, not ownership.
func minMeetingRooms(_ intervals: [[Int]]) -> Int {
let starts = intervals.map { $0[0] }.sorted()
let ends = intervals.map { $0[1] }.sorted()
var rooms = 0
var e = 0
for start in starts {
if start < ends[e] {
rooms += 1 // meeting starts before the earliest one finishes
} else {
e += 1 // reuse the room that just freed up
}
}
return rooms
}
6. Meeting Rooms III
Hard · LC 2402
Given n rooms and meetings, each takes the lowest-numbered free room or waits for the earliest room to free, keeping its duration; return the room hosting the most meetings, lowest index on ties. Sort meetings by start and keep two heaps, free rooms by index and busy rooms by end time then index, releasing finished rooms before each assignment. When a meeting waits, its new end is the freed end time plus the original duration.
def most_booked(n: int, meetings: list[list[int]]) -> int:
"""LC 2402. Meeting Rooms III.
Each meeting takes the lowest-numbered free room, or waits for the
earliest room to free while keeping its DURATION. Sort meetings by
start and run two heaps: free room indices, and busy rooms as
(busy_until, room) so ties on time break toward the lower index.
Before each meeting, release every room already finished. Return
the room hosting the most meetings, lowest index on ties.
O(m log m + m log n) time, O(n) space.
"""
free_rooms = list(range(n)) # min-heap of free room indices
busy: list[tuple[int, int]] = [] # min-heap of (busy_until, room)
meetings_held = [0] * n
for start, end in sorted(meetings):
while busy and busy[0][0] <= start:
_, freed = heapq.heappop(busy)
heapq.heappush(free_rooms, freed) # finished: back in the index heap
if free_rooms:
room = heapq.heappop(free_rooms)
busy_until = end
else:
# all rooms busy: time jumps to the earliest finish, and the
# delayed meeting keeps its duration, not its original end
freed_at, room = heapq.heappop(busy)
busy_until = freed_at + (end - start)
meetings_held[room] += 1
heapq.heappush(busy, (busy_until, room))
return meetings_held.index(max(meetings_held)) # index() takes the lowest tie
// LC 2402. Sort meetings by start and keep two heaps: a min-heap of free room
// indices and a min-heap of (busyUntil, room) for occupied rooms. Before each
// meeting, release every room whose end time is at most the start; then take
// the lowest free room, or if none is free pop the earliest-ending busy room
// and delay the meeting, with new end = freed end + original duration. Delays
// compound, so end times need long long. Ties go to the lowest room index,
// which max_element's first-occurrence rule provides.
int mostBooked(int n, vector<vector<int>> meetings) {
sort(meetings.begin(), meetings.end());
priority_queue<int, vector<int>, greater<int>> freeRooms;
for (int r = 0; r < n; ++r) freeRooms.push(r);
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<pair<long long, int>>>
busy; // (busyUntil, room)
vector<int> count(n, 0);
for (const vector<int>& m : meetings) {
long long start = m[0], duration = m[1] - m[0];
while (!busy.empty() && busy.top().first <= start) { // release finished rooms
freeRooms.push(busy.top().second);
busy.pop();
}
int room;
long long finish;
if (!freeRooms.empty()) {
room = freeRooms.top();
freeRooms.pop();
finish = start + duration; // starts on time
} else {
room = busy.top().second; // wait for the earliest room to free
finish = busy.top().first + duration;
busy.pop();
}
++count[room];
busy.push({finish, room});
}
return static_cast<int>(max_element(count.begin(), count.end()) - count.begin());
}
/// LC 2402. Sort meetings by start and keep two min-heaps: free rooms by
/// index and busy rooms by (end time, index). Before each meeting, release
/// every room whose end is at or before the start; if none is free, pop the
/// earliest finisher and shift the meeting, keeping its DURATION -- the new
/// end is the freed time plus end - start. Times accumulate past i32, so the
/// busy heap holds i64 ends.
pub fn most_booked(n: i32, meetings: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let mut meetings: Vec<(i64, i64)> = meetings
.iter()
.map(|m| (m[0] as i64, m[1] as i64))
.collect();
meetings.sort_unstable();
let mut free: BinaryHeap<Reverse<usize>> = (0..n).map(Reverse).collect();
let mut busy: BinaryHeap<Reverse<(i64, usize)>> = BinaryHeap::new();
let mut held = vec![0u32; n];
for (start, end) in meetings {
while let Some(&Reverse((free_at, room))) = busy.peek() {
if free_at > start {
break;
}
busy.pop();
free.push(Reverse(room));
}
if let Some(Reverse(room)) = free.pop() {
held[room] += 1;
busy.push(Reverse((end, room)));
} else {
let Reverse((free_at, room)) = busy.pop().unwrap();
held[room] += 1;
busy.push(Reverse((free_at + end - start, room)));
}
}
let mut best = 0;
for room in 1..n {
if held[room] > held[best] {
best = room; // strict >: ties keep the lower index
}
}
best as i32
}
/** LC 2402. Sort by start; two min-heaps (free room indices, busy [busyUntil, room]) replay the rules. */
export function mostBooked(n: number, meetings: number[][]): number {
const free: number[] = []; // min-heap of free room indices
const pushFree = (room: number): void => {
free.push(room);
let child = free.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (free[parent] <= free[child]) break;
[free[parent], free[child]] = [free[child], free[parent]];
child = parent;
}
};
const popFree = (): number => {
const top = free[0];
const last = free.pop()!;
if (free.length > 0) {
free[0] = last;
let parent = 0;
for (;;) {
let lowest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < free.length && free[left] < free[lowest]) lowest = left;
if (right < free.length && free[right] < free[lowest]) lowest = right;
if (lowest === parent) break;
[free[parent], free[lowest]] = [free[lowest], free[parent]];
parent = lowest;
}
}
return top;
};
const busy: [number, number][] = []; // min-heap of [busyUntil, room], end time then index
const before = (a: [number, number], b: [number, number]): boolean =>
a[0] !== b[0] ? a[0] < b[0] : a[1] < b[1];
const pushBusy = (entry: [number, number]): void => {
busy.push(entry);
let child = busy.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (!before(busy[child], busy[parent])) break;
[busy[parent], busy[child]] = [busy[child], busy[parent]];
child = parent;
}
};
const popBusy = (): [number, number] => {
const top = busy[0];
const last = busy.pop()!;
if (busy.length > 0) {
busy[0] = last;
let parent = 0;
for (;;) {
let earliest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < busy.length && before(busy[left], busy[earliest])) earliest = left;
if (right < busy.length && before(busy[right], busy[earliest])) earliest = right;
if (earliest === parent) break;
[busy[parent], busy[earliest]] = [busy[earliest], busy[parent]];
parent = earliest;
}
}
return top;
};
for (let room = 0; room < n; room++) pushFree(room);
const counts = new Array<number>(n).fill(0);
const sorted = [...meetings].sort((a, b) => a[0] - b[0]);
for (const [start, end] of sorted) {
while (busy.length > 0 && busy[0][0] <= start) pushFree(popBusy()[1]); // release finished rooms first
if (free.length > 0) {
const room = popFree(); // the lowest-numbered free room
counts[room]++;
pushBusy([end, room]);
} else {
const [busyUntil, room] = popBusy(); // earliest to free, lowest index on ties
counts[room]++;
pushBusy([busyUntil + (end - start), room]); // a delayed meeting keeps its duration
}
}
let best = 0;
for (let room = 1; room < n; room++) {
if (counts[room] > counts[best]) best = room; // strict > keeps the lowest index on ties
}
return best;
}
// LC 2402. Sort meetings by start; a min-heap of free room indices plus a
// min-heap of (busyUntil, room). With no free room, the earliest-ending room
// hosts the delayed meeting, which keeps its duration, not its end.
func mostBooked(n int, meetings [][]int) int {
ordered := append([][]int(nil), meetings...)
sort.Slice(ordered, func(a, b int) bool {
if ordered[a][0] != ordered[b][0] {
return ordered[a][0] < ordered[b][0]
}
return ordered[a][1] < ordered[b][1]
})
freeRooms := make([]int, n) // 0..n-1 in order is already a valid min-heap
for r := 0; r < n; r++ {
freeRooms[r] = r
}
pushFree := func(v int) {
freeRooms = append(freeRooms, v)
for i := len(freeRooms) - 1; i > 0; {
parent := (i - 1) / 2
if freeRooms[parent] <= freeRooms[i] {
break
}
freeRooms[i], freeRooms[parent] = freeRooms[parent], freeRooms[i]
i = parent
}
}
popFree := func() int {
top := freeRooms[0]
last := len(freeRooms) - 1
freeRooms[0] = freeRooms[last]
freeRooms = freeRooms[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(freeRooms) && freeRooms[l] < freeRooms[next] {
next = l
}
if r := 2*i + 2; r < len(freeRooms) && freeRooms[r] < freeRooms[next] {
next = r
}
if next == i {
break
}
freeRooms[i], freeRooms[next] = freeRooms[next], freeRooms[i]
i = next
}
return top
}
busy := [][2]int{} // (busyUntil, room): ties on time break to the lower room
less := func(a, b [2]int) bool {
if a[0] != b[0] {
return a[0] < b[0]
}
return a[1] < b[1]
}
pushBusy := func(e [2]int) {
busy = append(busy, e)
for i := len(busy) - 1; i > 0; {
parent := (i - 1) / 2
if !less(busy[i], busy[parent]) {
break
}
busy[i], busy[parent] = busy[parent], busy[i]
i = parent
}
}
popBusy := func() [2]int {
top := busy[0]
last := len(busy) - 1
busy[0] = busy[last]
busy = busy[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(busy) && less(busy[l], busy[next]) {
next = l
}
if r := 2*i + 2; r < len(busy) && less(busy[r], busy[next]) {
next = r
}
if next == i {
break
}
busy[i], busy[next] = busy[next], busy[i]
i = next
}
return top
}
count := make([]int, n)
for _, m := range ordered {
start, duration := m[0], m[1]-m[0]
for len(busy) > 0 && busy[0][0] <= start { // release finished rooms
pushFree(popBusy()[1])
}
var room, finish int
if len(freeRooms) > 0 {
room = popFree()
finish = start + duration // starts on time
} else {
earliest := popBusy() // wait for the earliest room to free
room = earliest[1]
finish = earliest[0] + duration
}
count[room]++
pushBusy([2]int{finish, room})
}
best := 0
for r := 1; r < n; r++ {
if count[r] > count[best] { // strict: ties keep the lowest room index
best = r
}
}
return best
}
// LC 2402. Sort meetings by start and run two min-heaps: free room indices,
// and busy rooms as (busyUntil, room) so time ties break toward the lower
// index. A delayed meeting keeps its DURATION, not its original end.
func mostBooked(_ n: Int, _ meetings: [[Int]]) -> Int {
var freeRooms: [Int] = [] // min-heap of free room indices
var busy: [(Int, Int)] = [] // min-heap of (busyUntil, room)
func pushRoom(_ room: Int) {
freeRooms.append(room)
var child = freeRooms.count - 1
while child > 0 {
let parent = (child - 1) / 2
if freeRooms[parent] <= freeRooms[child] { break }
freeRooms.swapAt(parent, child)
child = parent
}
}
func popRoom() -> Int {
let top = freeRooms[0]
freeRooms[0] = freeRooms[freeRooms.count - 1]
freeRooms.removeLast()
var parent = 0
while true {
var smallest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < freeRooms.count && freeRooms[left] < freeRooms[smallest] { smallest = left }
if right < freeRooms.count && freeRooms[right] < freeRooms[smallest] { smallest = right }
if smallest == parent { break }
freeRooms.swapAt(parent, smallest)
parent = smallest
}
return top
}
func pushBusy(_ item: (Int, Int)) {
busy.append(item)
var child = busy.count - 1
while child > 0 {
let parent = (child - 1) / 2
if busy[parent] <= busy[child] { break }
busy.swapAt(parent, child)
child = parent
}
}
func popBusy() -> (Int, Int) {
let top = busy[0]
busy[0] = busy[busy.count - 1]
busy.removeLast()
var parent = 0
while true {
var smallest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < busy.count && busy[left] < busy[smallest] { smallest = left }
if right < busy.count && busy[right] < busy[smallest] { smallest = right }
if smallest == parent { break }
busy.swapAt(parent, smallest)
parent = smallest
}
return top
}
for room in 0..<n { pushRoom(room) }
var count = [Int](repeating: 0, count: n)
for m in meetings.sorted(by: { ($0[0], $0[1]) < ($1[0], $1[1]) }) {
let start = m[0]
let duration = m[1] - m[0]
while !busy.isEmpty && busy[0].0 <= start { // release finished rooms
pushRoom(popBusy().1)
}
let room: Int
let finish: Int
if !freeRooms.isEmpty {
room = popRoom()
finish = start + duration // starts on time
} else {
let (freedAt, freedRoom) = popBusy() // wait for the earliest room to free
room = freedRoom
finish = freedAt + duration
}
count[room] += 1
pushBusy((finish, room))
}
var best = 0
for room in 1..<n where count[room] > count[best] { best = room } // lowest index on ties
return best
}
7. Minimum Interval to Include Each Query
Hard · LC 1851
Given intervals and queries, return for each query the size of the smallest interval containing it, or -1. Sort intervals by start and process queries in ascending order, pushing every interval whose start is at or below the query into a min-heap keyed by size, then popping entries whose end is below the query. Lazy expiry lets each interval enter and leave the heap once, and answers must be restored to the original query order.
def min_interval(intervals: list[list[int]], queries: list[int]) -> list[int]:
"""LC 1851. Minimum Interval to Include Each Query.
Sort intervals by start and answer queries in ascending order: push
every interval whose start is at or below the query into a min-heap
keyed by (size, end), then read the smallest survivor. Expiry is
LAZY: an interval whose end is below the current query is useless
for every later (larger) query too, so it is popped only when it
surfaces at the heap top -- each interval enters and leaves the
heap once. Answers are restored to the original query order at the
end. O((n + q) log(n + q)) time, O(n + q) space.
"""
ordered = sorted(intervals)
candidates: list[tuple[int, int]] = [] # min-heap of (size, end)
answer_for: dict[int, int] = {}
i = 0
for query in sorted(queries):
while i < len(ordered) and ordered[i][0] <= query:
start, end = ordered[i]
heapq.heappush(candidates, (end - start + 1, end))
i += 1
# lazy removal: dead intervals (end < query) stay buried in the heap
# until they reach the top; queries ascend, so they never revive
while candidates and candidates[0][1] < query:
heapq.heappop(candidates)
answer_for[query] = candidates[0][0] if candidates else -1
return [answer_for[query] for query in queries]
// LC 1851. Sort intervals by start and process the queries in ascending order
// (remembering their original positions): push every interval whose start is
// at or below the query into a min-heap keyed by size, then lazily pop entries
// whose end has fallen below the query. Lazy expiry means each interval enters
// and leaves the heap at most once, giving O((n + q) log n); the answers are
// written back through the saved index order.
vector<int> minInterval(vector<vector<int>> intervals, vector<int> queries) {
sort(intervals.begin(), intervals.end());
int q = static_cast<int>(queries.size());
vector<int> order(q);
for (int i = 0; i < q; ++i) order[i] = i;
sort(order.begin(), order.end(),
[&](int a, int b) { return queries[a] < queries[b]; });
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>
heap; // (size, end)
vector<int> answers(q, -1);
int i = 0, n = static_cast<int>(intervals.size());
for (int qi : order) {
int query = queries[qi];
while (i < n && intervals[i][0] <= query) { // every interval starting by now
heap.push({intervals[i][1] - intervals[i][0] + 1, intervals[i][1]});
++i;
}
while (!heap.empty() && heap.top().second < query) heap.pop(); // lazy expiry
if (!heap.empty()) answers[qi] = heap.top().first;
}
return answers;
}
/// LC 1851. Sort intervals by start and process queries in ascending order
/// (remembering each query's original index), pushing every interval whose
/// start is at or below the query into a min-heap keyed by (size, end), then
/// lazily popping entries whose end is below the query. Each interval enters
/// and leaves the heap once, so the whole sweep is O((n + q) log n) plus the
/// sorts, and answers go back through the index mapping.
pub fn min_interval(intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
let mut intervals: Vec<(i32, i32)> = intervals.iter().map(|iv| (iv[0], iv[1])).collect();
intervals.sort_unstable();
let mut order: Vec<usize> = (0..queries.len()).collect();
order.sort_unstable_by_key(|&qi| queries[qi]);
let mut heap: BinaryHeap<Reverse<(i32, i32)>> = BinaryHeap::new(); // (size, end)
let mut answers = vec![-1; queries.len()];
let mut i = 0;
for &qi in &order {
let q = queries[qi];
while i < intervals.len() && intervals[i].0 <= q {
let (left, right) = intervals[i];
heap.push(Reverse((right - left + 1, right)));
i += 1;
}
while let Some(&Reverse((_, end))) = heap.peek() {
if end >= q {
break;
}
heap.pop(); // lazy expiry: ended before this (and every later) query
}
if let Some(&Reverse((size, _))) = heap.peek() {
answers[qi] = size;
}
}
answers
}
/** LC 1851. Sort intervals and queries; min-heap by size with lazy expiry of ends below the query. */
export function minInterval(intervals: number[][], queries: number[]): number[] {
const byStart = [...intervals].sort((a, b) => a[0] - b[0]);
const byQuery = queries.map((_, index) => index).sort((a, b) => queries[a] - queries[b]);
const heap: [number, number][] = []; // [size, end]; min-heap keyed by size
const push = (entry: [number, number]): void => {
heap.push(entry);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent][0] <= heap[child][0]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): void => {
const last = heap.pop()!;
if (heap.length === 0) return;
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left][0] < heap[smallest][0]) smallest = left;
if (right < heap.length && heap[right][0] < heap[smallest][0]) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
};
const answers = new Array<number>(queries.length).fill(-1); // restored to original query order
let next = 0; // next unprocessed position in byStart
for (const queryIndex of byQuery) {
const query = queries[queryIndex];
while (next < byStart.length && byStart[next][0] <= query) {
const [start, end] = byStart[next++];
push([end - start + 1, end]); // each interval enters the heap exactly once
}
while (heap.length > 0 && heap[0][1] < query) pop(); // lazy expiry: ended before this query
if (heap.length > 0) answers[queryIndex] = heap[0][0];
}
return answers;
}
// LC 1851. Sort intervals by start and answer queries ascending: push every
// interval starting by the query into a (size, end) min-heap, lazily expire
// ends below the query, then the root is the smallest cover.
func minInterval(intervals [][]int, queries []int) []int {
ordered := append([][]int(nil), intervals...)
sort.Slice(ordered, func(a, b int) bool {
if ordered[a][0] != ordered[b][0] {
return ordered[a][0] < ordered[b][0]
}
return ordered[a][1] < ordered[b][1]
})
q := len(queries)
order := make([]int, q)
for i := range order {
order[i] = i
}
sort.Slice(order, func(a, b int) bool { return queries[order[a]] < queries[order[b]] })
heap := [][2]int{} // (size, end)
less := func(a, b [2]int) bool {
if a[0] != b[0] {
return a[0] < b[0]
}
return a[1] < b[1]
}
push := func(e [2]int) {
heap = append(heap, e)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if !less(heap[i], heap[parent]) {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() [2]int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && less(heap[l], heap[next]) {
next = l
}
if r := 2*i + 2; r < len(heap) && less(heap[r], heap[next]) {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
answers := make([]int, q)
for i := range answers {
answers[i] = -1
}
i, n := 0, len(ordered)
for _, qi := range order {
query := queries[qi]
for i < n && ordered[i][0] <= query { // every interval starting by now
push([2]int{ordered[i][1] - ordered[i][0] + 1, ordered[i][1]})
i++
}
for len(heap) > 0 && heap[0][1] < query { // lazy expiry: dead for all later queries too
pop()
}
if len(heap) > 0 {
answers[qi] = heap[0][0]
}
}
return answers
}
// LC 1851. Sort intervals by start, answer queries ascending with a min-heap
// keyed (size, end), expiring dead intervals LAZILY: an end below the current
// query is useless for every later query too, so pop it only at the top.
func minInterval(_ intervals: [[Int]], _ queries: [Int]) -> [Int] {
let ordered = intervals.sorted { ($0[0], $0[1]) < ($1[0], $1[1]) }
let order = queries.indices.sorted { queries[$0] < queries[$1] }
var heap: [(Int, Int)] = [] // min-heap of (size, end)
func push(_ item: (Int, Int)) {
heap.append(item)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] <= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> (Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var smallest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] < heap[smallest] { smallest = left }
if right < heap.count && heap[right] < heap[smallest] { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
return top
}
var answers = [Int](repeating: -1, count: queries.count)
var i = 0
for qi in order {
let query = queries[qi]
while i < ordered.count && ordered[i][0] <= query { // every interval starting by now
push((ordered[i][1] - ordered[i][0] + 1, ordered[i][1]))
i += 1
}
while !heap.isEmpty && heap[0].1 < query { _ = pop() } // lazy expiry
if !heap.isEmpty { answers[qi] = heap[0].0 }
}
return answers
}