#include <stdlib.h>
/**
* Definition of Interval:
* typedef struct {
* int start, end;
* } Interval;
*/
static int cmpStart(const void *a, const void *b) {
const Interval *x = a, *y = b;
return (x->start > y->start) - (x->start < y->start);
}
static void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
static void push(int *heap, int *size, int x) {
int i = (*size)++;
heap[i] = x;
while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
swap(&heap[(i - 1) / 2], &heap[i]);
i = (i - 1) / 2;
}
}
static void pop(int *heap, int *size) {
heap[0] = heap[--(*size)];
int i = 0;
for (;;) {
int s = i, l = 2 * i + 1, r = l + 1;
if (l < *size && heap[l] < heap[s])
s = l;
if (r < *size && heap[r] < heap[s])
s = r;
if (s == i)
break;
swap(&heap[s], &heap[i]);
i = s;
}
}
int minMeetingRooms(Interval *intervals, int intervalsSize) {
int mx = 0, size = 0;
int *minHeap = malloc((intervalsSize + 1) * sizeof(int)); // end times
qsort(intervals, intervalsSize, sizeof(Interval), cmpStart);
for (int i = 0; i < intervalsSize; i++) {
while (size > 0 && minHeap[0] <= intervals[i].start)
pop(minHeap, &size);
push(minHeap, &size, intervals[i].end);
if (size > mx)
mx = size;
}
free(minHeap);
return mx;
}
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
/**
* Definition of Interval:
* class Interval {
* public:
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
class Solution {
public:
int minMeetingRooms(vector<Interval> &intervals) {
int mx = 0;
priority_queue<int, vector<int>, greater<>> minHeap;
sort(
intervals.begin(), intervals.end(),
[](const Interval &a, const Interval &b) { return a.start < b.start; });
for (const auto &i : intervals) {
while (!minHeap.empty() && minHeap.top() <= i.start)
minHeap.pop();
minHeap.push(i.end);
mx = max(mx, (int)minHeap.size());
}
return mx;
}
};
package intervals
import (
"container/heap"
"slices"
)
// Definition of Interval:
// type Interval struct {
// start int
// end int
// }
type endHeap []int
func (h endHeap) Len() int { return len(h) }
func (h endHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h endHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *endHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *endHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func minMeetingRooms(intervals []Interval) int {
mx := 0
minHeap := &endHeap{}
slices.SortFunc(intervals, func(a, b Interval) int { return a.start - b.start })
for _, i := range intervals {
for minHeap.Len() > 0 && (*minHeap)[0] <= i.start {
heap.Pop(minHeap)
}
heap.Push(minHeap, i.end)
mx = max(mx, minHeap.Len())
}
return mx
}
import java.util.List;
import java.util.PriorityQueue;
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
public int minMeetingRooms(List<Interval> intervals) {
int mx = 0;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
intervals.sort((a, b) -> Integer.compare(a.start, b.start));
for (Interval i : intervals) {
while (!minHeap.isEmpty() && minHeap.peek() <= i.start)
minHeap.poll();
minHeap.offer(i.end);
mx = Math.max(mx, minHeap.size());
}
return mx;
}
}
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
/**
* @param {Interval[]} intervals
* @returns {number}
*/
var minMeetingRooms = function (intervals) {
let mx = 0;
// binary min-heap of end times: JS has no built-in priority queue
const heap = [];
const push = (x) => {
heap.push(x);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
for (;;) {
let s = i;
const l = 2 * i + 1;
const r = l + 1;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
};
intervals.sort((a, b) => a.start - b.start);
for (const i of intervals) {
while (heap.length > 0 && heap[0] <= i.start) pop();
push(i.end);
mx = Math.max(mx, heap.length);
}
return mx;
};
import heapq
from typing import List
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
def minMeetingRooms(self, intervals: List[Interval]) -> int:
mx = 0
min_heap = [] # end times of the meetings still running
intervals.sort(key=lambda i: i.start)
for i in intervals:
while min_heap and min_heap[0] <= i.start:
heapq.heappop(min_heap)
heapq.heappush(min_heap, i.end)
mx = max(mx, len(min_heap))
return mx
use std::cmp::Reverse;
use std::collections::BinaryHeap;
// Definition of Interval:
// pub struct Interval {
// pub start: i32,
// pub end: i32,
// }
impl Solution {
pub fn min_meeting_rooms(mut intervals: Vec<Interval>) -> i32 {
let mut mx = 0;
let mut min_heap = BinaryHeap::new(); // Reverse makes it a min-heap
intervals.sort_by_key(|i| i.start);
for i in &intervals {
while min_heap.peek().is_some_and(|&Reverse(end)| end <= i.start) {
min_heap.pop();
}
min_heap.push(Reverse(i.end));
mx = mx.max(min_heap.len());
}
mx as i32
}
}