Merge Intervals

1def merge(intervals):2    if not intervals:3        return []4 5    intervals.sort(key=lambda pair: pair[0])6    merged = [list(intervals[0])]7 8    for start, end in intervals[1:]:9        last = merged[-1]10        if start <= last[1]:11            # Overlap. Extend, but never shrink: the current interval may12            # already reach further than this one does.13            last[1] = max(last[1], end)14        else:15            merged.append([start, end])16 17    return merged18 19 20def max_concurrent(intervals):21    """Sweep line: +1 at each start, -1 at each end."""22    events = []23    for start, end in intervals:24        events.append((start, 1))25        events.append((end, -1))26 27    # Ends sort before starts at the same instant, so a meeting ending as28    # another begins does not count as an overlap.29    events.sort(key=lambda e: (e[0], e[1]))30 31    active = best = 032    for _time, delta in events:33        active += delta34        best = max(best, active)35    return best