区间问题 Intervals¶
Table of Contents¶
- 57. Insert Interval (Medium)
- 56. Merge Intervals (Medium)
- 252. Meeting Rooms (Easy) 👑
- 253. Meeting Rooms II (Medium) 👑
- 254. Factor Combinations (Medium) 👑
57. Insert Interval¶
from typing import List
# Interval
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
n = len(intervals)
if n == 0:
return [newInterval]
if newInterval[1] < intervals[0][0]:
return [newInterval] + intervals
if newInterval[0] > intervals[-1][1]:
return intervals + [newInterval]
i = 0
result = []
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
while i < n:
result.append(intervals[i])
i += 1
return result
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
print(insert(intervals, newInterval)) # [[1, 5], [6, 9]]
56. Merge Intervals¶
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""
Merge all overlapping intervals.
| G----H
| E===========F
| C--------D
| A========B
|
|-----------------------------------
Draw the above to explain the process to the interviewer.
Time complexity: O(nlogn) due to sorting.
Space complexity: O(n) for the result list.
"""
n = len(intervals)
if n <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, n):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& range : intervals) {
if (!res.empty() && range[0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], range[1]);
} else {
res.emplace_back(range);
}
}
return res;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> res = merge(intervals);
for (auto& range : res) {
cout << range[0] << ", " << range[1] << endl;
}
return 0;
}
252. Meeting Rooms 👑¶
from typing import List
# Interval
def canAttendMeetings(intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
n = len(intervals)
if n <= 1:
return True
for i in range(1, n):
if intervals[i][0] < intervals[i - 1][1]:
return False
return True
if __name__ == "__main__":
intervals = [[0, 30], [5, 10], [15, 20]]
assert not canAttendMeetings(intervals)
253. Meeting Rooms II 👑¶
from heapq import heappop, heappush
from typing import List
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
"""Min Heap: O(n log n) time, O(n) space.
Track active meeting end times; the peak heap size is the minimum
number of rooms required.
Timeline (letters mark meeting endpoints):
| G----H
| E-----------F
| C--------------D
| A----------B
+----------------------------------
Heap simulation (earliest end first):
A: push B -> [B]
C: C < B, push D -> [B, D]
E: pop B and D, push F -> [F]
G: G < F, push H -> [H, F]
The peak heap size is 2, so two rooms are required.
"""
ends = []
res = 0
for start, end in sorted(intervals):
while ends and ends[0] <= start:
heappop(ends)
heappush(ends, end)
res = max(res, len(ends))
return res
def test_min_meeting_rooms():
s = Solution()
for fn in (s.minMeetingRooms,):
assert fn([]) == 0
assert fn([[0, 30], [5, 10], [15, 20]]) == 2
assert fn([[7, 10], [2, 4]]) == 1
assert fn([[1, 5], [5, 10], [5, 8]]) == 2