2. Array - Intervals

2.1 Interval的Overlap 和 Merge

# 假定有interval_a 和 interval_b

low = max(interval_a[0], interval_b[0])
high = min(interval_a[1], interval_b[1])

if low < high:  # or low <= high
    # overlap
    overlap = [low, high]
    
    # merge (if the intervals has overlap)
    merged = [None, None]
    merged[0] = min(interval_a[0], interval_a[0])
    merged[1] = max(interval_b[1], interval_b[1])

2.2 Overlapping Interval List 问题

本质上这类问题是以时间为横轴的sliding window问题

2.2.1 问题要求只和区间本身有关的问题 - 可以仅从start_idx和end_idx就可以知晓的（区间index，或区间长度，或区间是否存在的问题）。

首先sort所有的interval，维护一个window变量代表当前所求的时间窗口，然后每个interval的开始和结束，要么close当前的window新建一个新window，要么是延伸当前的window或推迟将来的window。

e.g. https://leetcode.com/problems/merge-intervals/

# TEMPLATE
def merge(intervals):
    if len(intervals) == 0:
        return []
    
    intervals = sorted(intervals)
    
    output = []
    window = intervals[0]
    
    for idx in range(1, len(intervals)):
        interval = intervals[idx]
        # has no overlap
        if window[1] < interval[0]:
            output.append(window)
            window = interval
        
        window[1] = max(window[1], interval[1])
    
    # last window
    output.append(window)
    return output

2.2.2 问题要求只和区间本身有关的问题（区间index，或区间长度，或区间是否存在的问题）。

首先sort所有的interval，将每个interval拆解成两个event，这些event会影响整个program的某些状态，比如 overlap_count，然后按照时间序遍历所有event，根据event来open和close window，然后判断window和状态变量是否满足所需的条件。

# TEMPLATE
class Event:
    def __init__(self, time):
        self.time = time
        
class BusyEvent(Event):
    pass

class FreeEvent(Event):
    pass
    
def eligible_windows(schedule):
    events = []
    for interval in schedule:
        events.append(BusyEvent(interval[0]))
        events.append(FreeEvent(interval[1]))
        
    events.sort(lambda event: event.time)
    
    output = []
    window = []
    busy_count = 0
    
    for event in events:
        if isinstance(event, BusyEvent):
            busy_count += 1
        else:
            busy_count -= 1
        
        # open window
        if busy_count == 0 and len(window) == 0:
            window.append(event.time)
        elif busy_count > 0 and len(window) == 1:
            window.append(event.time)
            if window[0] < window[1]:
                output.append(window) 
            window = []
        
    return output