How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Merge overlapping time intervals efficiently

Q: Merge overlapping time intervals efficiently

This question evaluates a candidate's understanding of interval merging, sorting strategies, edge-case handling (including touching endpoints and zero-length intervals), and attention to time and space complexity when manipulating ranges.

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a list of closed intervals [start, end] with 0 <= start <= end, merge all intervals that overlap or touch and return a minimal set of non-overlapping intervals sorted by start. Implement an algorithm with O(n log n) time (due to sorting) and as little extra space as possible beyond the output. Clarify how to treat touching endpoints (e.g., [1,3] and [3,5]), zero-length intervals (e.g., [4,4]), and invalid inputs. Provide tests for nested intervals, duplicates, already-sorted input, reverse-sorted input, and large inputs (up to 1e5 intervals).

Quick Answer: This question evaluates a candidate's understanding of interval merging, sorting strategies, edge-case handling (including touching endpoints and zero-length intervals), and attention to time and space complexity when manipulating ranges.

Given a collection of closed intervals [start, end], merge every pair of intervals that overlap or touch, and return the minimal set of non-overlapping intervals sorted by start time. Because the intervals are closed, touching endpoints count as connected. For example, [1,3] and [3,5] must be merged into [1,5]. Zero-length intervals such as [4,4] are valid and should be handled normally. If the input is empty, return an empty list. If any interval is malformed, contains non-integer values, has negative values, or has start > end, raise a ValueError. Your algorithm should run in O(n log n) time, which is optimal here because sorting is required in the general case. To minimize extra space, you may reorder the input intervals in place.

Constraints

0 <= n <= 100000, where n is the number of intervals
0 <= start <= end <= 10^9 for every valid interval
Each interval must contain exactly two integers; otherwise raise ValueError

Examples

Input: ([] ,)

Expected Output: []

Explanation: An empty input has no intervals to merge, so the result is an empty list.

Input: ([[1,10],[2,3],[4,8],[9,10]],)

Expected Output: [[1,10]]

Explanation: All intervals are contained within or touch the outer interval [1,10], so they collapse into one interval.

Input: ([[1,3],[1,3],[3,5],[4,4],[7,7],[7,7]],)

Expected Output: [[1,5],[7,7]]

Explanation: Duplicates merge naturally, [1,3] touches [3,5], and [4,4] lies inside the merged interval. The two [7,7] intervals merge into one.

Input: ([[0,1],[2,2],[2,4],[6,8]],)

Expected Output: [[0,1],[2,4],[6,8]]

Explanation: The input is already sorted. Only [2,2] and [2,4] touch and merge.

Input: ([[8,10],[6,7],[3,5],[1,3]],)

Expected Output: [[1,5],[6,7],[8,10]]

Explanation: After sorting, [1,3] touches [3,5] and becomes [1,5]. The other intervals stay separate.

Input: ([[30,31],[27,29],[29,30],[20,20],[18,19],[15,17],[17,18],[12,14],[10,11],[11,12],[5,5],[4,6],[2,3],[1,2],[40,45],[44,50]],)

Expected Output: [[1,3],[4,6],[10,14],[15,19],[20,20],[27,31],[40,50]]

Explanation: This larger mixed case creates several chains of touching or overlapping intervals. The same O(n log n) approach scales to inputs as large as 100000 intervals.

Hints

Sort the intervals by their start value first. After that, you only need one left-to-right pass to merge them.
Keep the last merged interval in the output and compare the next interval's start against its end. For closed intervals, start <= end means they should merge.

Quick Overview

This question evaluates a candidate's understanding of interval merging, sorting strategies, edge-case handling (including touching endpoints and zero-length intervals), and attention to time and space complexity when manipulating ranges.