Interval Questions¶
Meeting Room I, II¶
Merge Intervals, Insert Interval¶
Put them into 3 parts! Think about the condition when 2 overlaps Sort can help simplify the condition
Find least number of intervals from A that can fully cover B¶
# Given a list of intervals A and one interval B, find the least # number of intervals from A that can fully cover B. # # If cannot find any result, just return 0; # # For example: # Given A=[[0,3],[3,4],[4,6],[2,7]] B=[0,6] return 2 since we can use [0,3] [2,7] to cover the B # Given A=[[0,3],[4,7]] B=[0,6] return 0 since we cannot find any interval combination from A to cover the B
Greedy: choose furthest range
sort by start, upon same, by end(not necessary) find eligible intervals for start: base start = target.start definition of eligible intervals: x is eligible if x.start <= start && x.end > start special case: if the earliest start > start, no ans, break!!! Among all eligible intervals, choose the one that has the furthest range count++; if(furthest range >= target.end) -> ans found update start to furthest range repeat the iteration
Solution:
def findMinIntervals(intervals, target):
"""
:type intervals: List[[int, int]]
:type target: list[int, int]
:rtype: int
"""
intervals.sort()
res = 0
cur_target = target[0]
i = 0
max_step = 0
while i < len(intervals) and cur_target < target[1]:
if intervals[i][0] > cur_target:
return 0
while i < len(intervals) and intervals[i][0] <= cur_target:
max_step = max(max_step, intervals[i][1])
i += 1
cur_target = max_step
res += 1
return res if cur_target >= target[1] else 0