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