Interval¶
Table of Contents¶
- 163. Missing Ranges (Easy) 👑
- 252. Meeting Rooms (Easy) 👑
- 253. Meeting Rooms II (Medium) 👑
- 616. Add Bold Tag in String (Medium) 👑
- 1272. Remove Interval (Medium) 👑
163. Missing Ranges 👑¶
from typing import List
def findMissingRanges(nums: List[int], lower: int, upper: int) -> List[List[int]]:
n = len(nums)
res = []
if n == 0:
return [[lower, upper]]
# start
if nums[0] > lower:
res.append([lower, nums[0] - 1])
# middle
for i in range(n - 1):
if nums[i] + 1 < nums[i + 1]:
res.append([nums[i] + 1, nums[i + 1] - 1])
# end
if nums[-1] < upper:
res.append([nums[-1] + 1, upper])
return res
def findMissingRangesCompact(nums: List[int], lower: int, upper: int) -> List[List[int]]:
res = []
for num in nums + [upper + 1]:
if num > lower:
res.append([lower, num - 1])
lower = num + 1
return res
if __name__ == "__main__":
nums = [0, 1, 3, 50, 75]
lower = 0
upper = 99
assert findMissingRanges(nums, lower, upper) == [
[2, 2],
[4, 49],
[51, 74],
[76, 99],
]
assert findMissingRangesCompact(nums, lower, upper) == [
[2, 2],
[4, 49],
[51, 74],
[76, 99],
]
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