def merge_intervals(intervals):
    if not intervals:
        return []
    ordered = sorted(intervals, key=lambda pair: pair[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged
def insert_interval(intervals, new):
    result = []
    start, end = new[0], new[1]
    i, n = 0, len(intervals)
    while i < n and intervals[i][1] < start:
        result.append(list(intervals[i]))
        i += 1
    while i < n and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])
    while i < n:
        result.append(list(intervals[i]))
        i += 1
    return result
def can_attend_all(meetings):
    ordered = sorted(meetings, key=lambda pair: pair[0])
    for i in range(1, len(ordered)):
        if ordered[i][0] < ordered[i - 1][1]:
            return False
    return True
def min_meeting_rooms(meetings):
    if not meetings:
        return 0
    starts = sorted(m[0] for m in meetings)
    ends = sorted(m[1] for m in meetings)
    rooms, best = 0, 0
    i, j, n = 0, 0, len(meetings)
    while i < n:
        if starts[i] < ends[j]:
            rooms += 1
            best = max(best, rooms)
            i += 1
        else:
            rooms -= 1
            j += 1
    return best
def max_non_overlapping(intervals):
    """Return the size of the largest mutually non-overlapping subset.

    intervals is a list of [start, end] pairs. Intervals that only touch
    at an endpoint may both be chosen. Use activity selection: sort by
    end time and greedily keep each interval that starts at or after the
    last kept interval ends.
    """
    # TODO: sort by end, greedily pick compatible intervals, count them
    pass