# The Schedule Cleaner > Overlapping sessions. One clean line. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L4 · Asked in: Netflix ## Problem You're consolidating playback sessions from a streaming service's event logs, where each session in `intervals` is a `[start, end]` timestamp pair that may arrive in any order. Collapse every run of overlapping sessions into one continuous span and return the spans sorted by start time. Sessions that only touch at an endpoint still belong to the same span, so `[1, 3]` and `[3, 5]` become `[1, 5]`. ## Example Input: ``` intervals = [[1,6],[2,6],[8,10],[15,18]] ``` Output: ``` [[1,6],[8,10],[15,18]] ``` ## Worked solution and explanation ### What this really is Strip the streaming costume and this is range coalescing: turning a pile of possibly-overlapping sessions into the fewest spans that cover exactly the same time. Anyone can write the comparison between two intervals. What separates candidates is two things. Do they put the sessions in start order before comparing anything? And do they treat a span's end as something that only ever grows? Skip the sort and a later session that arrives first hides a real overlap. Overwrite the end instead of keeping the larger one and a short session nested inside a long one, like `[2, 4]` inside `[1, 10]`, chops the span down to `[1, 4]`. > **Two cases, never three** > > Once the sessions are in start order, each one either extends the last span you kept or opens a new one. There is no third case, and you never look further back than `merged[-1]`. --- ### Walking the merge #### Step 1: Sort by start time Sorting by start guarantees that any session able to overlap the current span is the very next one you visit. That is what turns an all-pairs comparison into a single forward pass. #### Step 2: Keep the last span open Walk the sorted sessions carrying a list of merged spans. The open span is always the last one you appended, so the only thing you ever compare against is `merged[-1]`. #### Step 3: Extend or open The overlap test is `start <= merged[-1][1]`. It uses `<=`, not `<`, so touching endpoints merge. On overlap, push the end out with `max(merged[-1][1], end)`, so a nested session like `[2, 4]` inside `[1, 10]` cannot shrink the span. Otherwise the session opens a new span. --- ### The solution **Sort then linear merge pass** ```python def merge_intervals(intervals): merged = [] for start, end in sorted(intervals): if merged and start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end]) return merged ``` *`sorted()` builds a new list, so the caller's input is never reordered in place.* > **The sort is the whole bill** > > **O(n log n)** for the sort, then one O(n) pass. Space is O(n) for the output and nothing beyond it, because the merge edits the last span of the result in place. A million sessions sort in well under a second. > **Sorting first is the senior signal** > > The tell is whether you sort before you compare. A candidate who jumps into pairwise comparisons writes an O(n^2) solution that still misses overlaps when a later session arrives first. Naming the sort up front, and saying it makes every possible overlap adjacent, is what reads as senior. > **Strict `<` splits touching sessions** > > The common slip is writing the overlap test as `start < merged[-1][1]`. Sessions `[1, 3]` and `[3, 5]` share the point 3 and must merge to `[1, 5]`; a strict `<` returns them as two spans. The other classic miss is `merged[-1][1] = end` instead of `max(...)`, which shrinks the span whenever a shorter nested session follows. --- ## Common follow-up questions - What if the list is already merged and you only need to insert one new interval into it? _(Tests the insert-interval variant: a single pass against an already-merged list.)_ - What if each session carried a label and you needed to know which originals composed each merged span? _(Tests carrying provenance metadata alongside the merge.)_ - What if sessions arrived as an unbounded stream instead of a finite list? _(Tests maintaining a sorted structure that merges on the fly.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_schedule_cleaner) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.