Description
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1
Constraints:
1 <= intervals.length <= 1040 <= starti < endi <= 106
Solutions
Solution 1: Difference Array
We can implement this using a difference array.
First, we find the maximum end time of all the meetings, denoted as m. Then, we create a difference array d of length m + 1. For each meeting, we add to the corresponding positions in the difference array: d[l] = d[l] + 1 for the start time, and d[r] = d[r] - 1 for the end time.
Next, we calculate the prefix sum of the difference array and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.
The time complexity is O(n + m) and the space complexity is O(m), where n is the number of meetings and m is the maximum end time.
PythonJavaC++GoTypeScriptRust
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
m = max(e[1] for e in intervals)
d = [0] * (m + 1)
for l, r in intervals:
d[l] += 1
d[r] -= 1
ans = s = 0
for v in d:
s += v
ans = max(ans, s)
return ans(code-box)
class Solution {
public int minMeetingRooms(int[][] intervals) {
int m = 0;
for (var e : intervals) {
m = Math.max(m, e[1]);
}
int[] d = new int[m + 1];
for (var e : intervals) {
++d[e[0]];
--d[e[1]];
}
int ans = 0, s = 0;
for (int v : d) {
s += v;
ans = Math.max(ans, s);
}
return ans;
}
}(code-box)
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
int m = 0;
for (const auto& e : intervals) {
m = max(m, e[1]);
}
vector<int> d(m + 1);
for (const auto& e : intervals) {
d[e[0]]++;
d[e[1]]--;
}
int ans = 0, s = 0;
for (int v : d) {
s += v;
ans = max(ans, s);
}
return ans;
}
};(code-box)
func minMeetingRooms(intervals [][]int) (ans int) {
m := 0
for _, e := range intervals {
m = max(m, e[1])
}
d := make([]int, m+1)
for _, e := range intervals {
d[e[0]]++
d[e[1]]--
}
s := 0
for _, v := range d {
s += v
ans = max(ans, s)
}
return
}(code-box)
function minMeetingRooms(intervals: number[][]): number {
const m = Math.max(...intervals.map(([_, r]) => r));
const d: number[] = Array(m + 1).fill(0);
for (const [l, r] of intervals) {
d[l]++;
d[r]--;
}
let [ans, s] = [0, 0];
for (const v of d) {
s += v;
ans = Math.max(ans, s);
}
return ans;
}(code-box)
impl Solution {
pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
let mut m = 0;
for e in &intervals {
m = m.max(e[1]);
}
let mut d = vec![0; (m + 1) as usize];
for e in intervals {
d[e[0] as usize] += 1;
d[e[1] as usize] -= 1;
}
let mut ans = 0;
let mut s = 0;
for v in d {
s += v;
ans = ans.max(s);
}
ans
}
}(code-box)
Solution 2: Difference (Hash Map)
If the meeting times span a large range, we can use a hash map instead of a difference array.
First, we create a hash map d, where we add to the corresponding positions for each meeting's start time and end time: d[l] = d[l] + 1 for the start time, and d[r] = d[r] - 1 for the end time.
Then, we sort the hash map by its keys, calculate the prefix sum of the hash map, and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.
The time complexity is O(n × log n) and the space complexity is O(n), where n is the number of meetings.
PythonJavaC++GoTypeScriptRust
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
d = defaultdict(int)
for l, r in intervals:
d[l] += 1
d[r] -= 1
ans = s = 0
for _, v in sorted(d.items()):
s += v
ans = max(ans, s)
return ans(code-box)
class Solution {
public int minMeetingRooms(int[][] intervals) {
Map<Integer, Integer> d = new TreeMap<>();
for (var e : intervals) {
d.merge(e[0], 1, Integer::sum);
d.merge(e[1], -1, Integer::sum);
}
int ans = 0, s = 0;
for (var e : d.values()) {
s += e;
ans = Math.max(ans, s);
}
return ans;
}
}(code-box)
class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
map<int, int> d;
for (const auto& e : intervals) {
d[e[0]]++;
d[e[1]]--;
}
int ans = 0, s = 0;
for (auto& [_, v] : d) {
s += v;
ans = max(ans, s);
}
return ans;
}
};(code-box)
func minMeetingRooms(intervals [][]int) (ans int) {
d := make(map[int]int)
for _, e := range intervals {
d[e[0]]++
d[e[1]]--
}
keys := make([]int, 0, len(d))
for k := range d {
keys = append(keys, k)
}
sort.Ints(keys)
s := 0
for _, k := range keys {
s += d[k]
ans = max(ans, s)
}
return
}(code-box)
function minMeetingRooms(intervals: number[][]): number {
const d: { [key: number]: number } = {};
for (const [l, r] of intervals) {
d[l] = (d[l] || 0) + 1;
d[r] = (d[r] || 0) - 1;
}
let [ans, s] = [0, 0];
const keys = Object.keys(d)
.map(Number)
.sort((a, b) => a - b);
for (const k of keys) {
s += d[k];
ans = Math.max(ans, s);
}
return ans;
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
let mut d: HashMap<i32, i32> = HashMap::new();
for interval in intervals {
let (l, r) = (interval[0], interval[1]);
*d.entry(l).or_insert(0) += 1;
*d.entry(r).or_insert(0) -= 1;
}
let mut times: Vec<i32> = d.keys().cloned().collect();
times.sort();
let mut ans = 0;
let mut s = 0;
for time in times {
s += d[&time];
ans = ans.max(s);
}
ans
}
}(code-box)
