Meeting Room II
Minimizing Interval Removals to Ensure Non-Overlapping Intervals
In problems involving intervals, it’s important to efficiently manage and handle cases where intervals might overlap.
In this article, we’ll look at a problem where the goal is to determine the minimum number of intervals that need to be removed to ensure that the remaining intervals are non-overlapping.
Problem Description
You are given an array of meeting time intervals, where each interval is represented as [start, end].
Each interval signifies the start and end times of a meeting. Your goal is to determine the minimum number of days required to schedule all the meetings without conflicts.
Key Points:
- Meetings that overlap cannot be scheduled on the same day.
- Meetings that touch at their boundaries (e.g.,
[0,8]and[8,10]) are not considered overlapping.
Constraints:
- 0 <= intervals.length <= 500
- 0 <= intervals[i].start < intervals[i].end <= 1,000,000
Example 1
Input: intervals = [(0,40),(5,10),(15,20)]
Output: 2
Explanation:
- day1: (0,40)
day2: (5,10),(15,20)
Example 2
Input: intervals = [(4,9)]
Output: 1
Explanation:
- (0,8),(8,10) is not considered a conflict at 8
Approach to Solve the Problem
The problem can be solved efficiently using the concept of interval graph coloring. Here’s how:
Step 1: Understand the Problem as a Graph
- Treat each meeting as a node in a graph.
- Create an edge between two nodes if their intervals overlap.
For example:(0,40)and(5,10)overlap, so they are connected by an edge.
Step 2: Determine the Minimum Number of Colors
- The number of colors required to color the graph such that no two adjacent nodes have the same color is equal to the graph’s chromatic number.
In our case, the chromatic number corresponds to the minimum number of days required to schedule all meetings without conflicts.
Step 3: Leverage a Sweep Line Algorithm
Instead of explicitly building a graph, we can use a sweep line algorithm to compute the maximum number of overlapping intervals at any given time. This number directly translates to the minimum number of days needed.
Algorithm
Extract Start and End Times:
Create two separate lists:- A list of all start times, marked as
+1to indicate an active meeting. - A list of all end times, marked as
-1to indicate a meeting ending.
- A list of all start times, marked as
Sort the Events:
Sort all events (start and end times) by time. If two events occur at the same time, prioritize theendevent over thestart.Track Overlaps:
Use a counter to track the number of active meetings at any point. The maximum value of this counter gives the number of days req
There are mainly Four approach to solve this problem –
- Min Heap
- Sweep Line Algorithm
- Two Pointers
- Greedy
1. Min Heap
- Time complexity: O(nlogn)
- Space complexity: O(n)
Python
C++
Java
JavaScript
Python
"""
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:
intervals.sort(key=lambda x: x.start)
min_heap = []
for interval in intervals:
if min_heap and min_heap[0] <= interval.start:
heapq.heappop(min_heap)
heapq.heappush(min_heap, interval.end)
return len(min_heap)
C++
/**
* 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& intervals) {
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a.start < b.start;
});
priority_queue, greater> minHeap;
for (const auto& interval : intervals) {
if (!minHeap.empty() && minHeap.top() <= interval.start) {
minHeap.pop();
}
minHeap.push(interval.end);
}
return minHeap.size();
}
}; Java
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public int minMeetingRooms(List intervals) {
intervals.sort((a, b) -> a.start - b.start);
PriorityQueue minHeap = new PriorityQueue<>();
for (Interval interval : intervals) {
if (!minHeap.isEmpty() && minHeap.peek() <= interval.start) {
minHeap.poll();
}
minHeap.offer(interval.end);
}
return minHeap.size();
}
} JavaScript
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
/**
* @param {Interval[]} intervals
* @returns {number}
*/
minMeetingRooms(intervals) {
intervals.sort((a, b) => a.start - b.start);
const minHeap = new MinPriorityQueue();
for (const interval of intervals) {
if (!minHeap.isEmpty() && minHeap.front() <= interval.start) {
minHeap.pop();
}
minHeap.push(interval.end);
}
return minHeap.size();
}
}2. Sweep Line Algorithm
Time & Space Complexity
- Time complexity: O(nlogn)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
/**
* 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& intervals) {
map mp;
for (auto& i : intervals) {
mp[i.start]++;
mp[i.end]--;
}
int prev = 0, res = 0;
for (auto& [key, value] : mp) {
prev += value;
res = max(res, prev);
}
return res;
}
}; Java
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public int minMeetingRooms(List intervals) {
TreeMap mp = new TreeMap<>();
for (Interval i : intervals) {
mp.put(i.start, mp.getOrDefault(i.start, 0) + 1);
mp.put(i.end, mp.getOrDefault(i.end, 0) - 1);
}
int prev = 0;
int res = 0;
for (int key : mp.keySet()) {
prev += mp.get(key);
res = Math.max(res, prev);
}
return res;
}
}
Python
"""
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:
mp = defaultdict(int)
for i in intervals:
mp[i.start] += 1
mp[i.end] -= 1
prev = 0
res = 0
for i in sorted(mp.keys()):
prev += mp[i]
res = max(res, prev)
return resJavaScript
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
/**
* @param {Interval[]} intervals
* @returns {number}
*/
minMeetingRooms(intervals) {
const mp = new Map();
for (const i of intervals) {
mp.set(i.start, (mp.get(i.start) || 0) + 1);
mp.set(i.end, (mp.get(i.end) || 0) - 1);
}
const sortedKeys = Array.from(mp.keys()).sort((a, b) => a - b);
let prev = 0, res = 0;
for (const key of sortedKeys) {
prev += mp.get(key);
res = Math.max(res, prev);
}
return res;
}
}3. Two Pointers
- Time complexity: O(nlogn)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
/**
* 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& intervals) {
vector start, end;
for (const auto& i : intervals) {
start.push_back(i.start);
end.push_back(i.end);
}
sort(start.begin(), start.end());
sort(end.begin(), end.end());
int res = 0, count = 0, s = 0, e = 0;
while (s < intervals.size()) {
if (start[s] < end[e]) {
s++;
count++;
} else {
e++;
count--;
}
res = max(res, count);
}
return res;
}
};
Java
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public int minMeetingRooms(List intervals) {
int n = intervals.size();
int[] start = new int[n];
int[] end = new int[n];
for (int i = 0; i < n; i++) {
start[i] = intervals.get(i).start;
end[i] = intervals.get(i).end;
}
Arrays.sort(start);
Arrays.sort(end);
int res = 0, count = 0, s = 0, e = 0;
while (s < n) {
if (start[s] < end[e]) {
s++;
count++;
} else {
e++;
count--;
}
res = Math.max(res, count);
}
return res;
}
}
Python
"""
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:
start = sorted([i.start for i in intervals])
end = sorted([i.end for i in intervals])
res = count = 0
s = e = 0
while s < len(intervals):
if start[s] < end[e]:
s += 1
count += 1
else:
e += 1
count -= 1
res = max(res, count)
return resJavaScript
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
/**
* @param {Interval[]} intervals
* @returns {number}
*/
minMeetingRooms(intervals) {
const start = intervals.map(i => i.start).sort((a, b) => a - b);
const end = intervals.map(i => i.end).sort((a, b) => a - b);
let res = 0, count = 0, s = 0, e = 0;
while (s < intervals.length) {
if (start[s] < end[e]) {
s++;
count++;
} else {
e++;
count--;
}
res = Math.max(res, count);
}
return res;
}
}4. Greedy
- Time complexity: O(nlogn)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
/**
* 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& intervals) {
vector> time;
for (const auto& i : intervals) {
time.push_back({i.start, 1});
time.push_back({i.end, -1});
}
sort(time.begin(), time.end(), [](auto& a, auto& b) {
return a.first == b.first ? a.second < b.second : a.first < b.first;
});
int res = 0, count = 0;
for (const auto& t : time) {
count += t.second;
res = max(res, count);
}
return res;
}
};
Java
/**
* Definition of Interval:
* public class Interval {
* public int start, end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
public int minMeetingRooms(List intervals) {
List time = new ArrayList<>();
for (Interval i : intervals) {
time.add(new int[] { i.start, 1 });
time.add(new int[] { i.end, -1 });
}
time.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int res = 0, count = 0;
for (int[] t : time) {
count += t[1];
res = Math.max(res, count);
}
return res;
}
}
Python
"""
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:
time = []
for i in intervals:
time.append((i.start, 1))
time.append((i.end, -1))
time.sort(key=lambda x: (x[0], x[1]))
res = count = 0
for t in time:
count += t[1]
res = max(res, count)
return resJavaScript
/**
* Definition of Interval:
* class Interval {
* constructor(start, end) {
* this.start = start;
* this.end = end;
* }
* }
*/
class Solution {
/**
* @param {Interval[]} intervals
* @returns {number}
*/
minMeetingRooms(intervals) {
const time = [];
for (const i of intervals) {
time.push([i.start, 1]);
time.push([i.end, -1]);
}
time.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);
let res = 0, count = 0;
for (const t of time) {
count += t[1];
res = Math.max(res, count);
}
return res;
}
}
