Merge Intervals and Missing Value

MediumPython

Problem

A Snapchat playback timeline contains recorded half-open intervals [start, end). Given the full timeline range and recorded intervals, merge all overlapping or touching intervals and find the single missing interval inside the timeline.

Implement merge_and_find_missing(intervals, timeline_start, timeline_end). Return a dictionary with merged, the sorted union of recorded intervals, and missing, the only uncovered interval [start, end] within the timeline.

The input is guaranteed to contain exactly one non-empty missing interval. Intervals are half-open, so [2, 5) and [5, 8) have no gap and must be merged into [2, 8). All recorded intervals lie within the timeline bounds.

Formal Specification

intervals: a list of integer pairs [start, end], representing [start, end).
timeline_start, timeline_end: integers with timeline_start < timeline_end.
Return {"merged": [[s1, e1], ...], "missing": [a, b]}.

Constraints

1 <= len(intervals) <= 10^5
0 <= timeline_start < timeline_end <= 10^9
timeline_start <= start < end <= timeline_end
Exactly one non-empty missing interval exists

Function Signature

def merge_and_find_missing(intervals, timeline_start, timeline_end):

Formal Specification

intervals: a list of integer pairs [start, end], representing [start, end).
timeline_start, timeline_end: integers with timeline_start < timeline_end.
Return {"merged": [[s1, e1], ...], "missing": [a, b]}.