Merge two interval lists into a union
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two lists of closed intervals [start, end]. Each list is individually sorted by start and contains non-overlapping intervals. Merge the two lists into a single list representing the union of all intervals, returning a minimal set of non-overlapping intervals sorted by start. Specify how you handle touching boundaries (e.g., [1,3] and [3,5]), empty inputs, and invalid intervals (start > end). State the time and space complexity and outline an O(m + n) two-pointer approach.
Quick Answer: This question evaluates a candidate's ability to implement interval merging algorithms, reason about edge cases such as touching boundaries, empty inputs, and invalid intervals, and perform time and space complexity analysis.
You are given two lists of closed intervals `[start, end]`. Each list is individually sorted by start and contains non-overlapping intervals. Merge the two lists into a single list representing the union of all intervals, returning a minimal set of non-overlapping intervals sorted by start.
Use an O(m + n) two-pointer sweep: repeatedly take the interval with the smaller start from the front of either list, then either extend the last interval in the output (if it overlaps or touches) or append it as a new interval.
Boundary rules to handle:
- Touching boundaries merge: `[1,3]` and `[3,5]` become `[1,5]` (closed intervals share the point 3).
- Empty inputs: if both lists are empty, return an empty list; if one is empty, the result is the other list (already minimal).
- Invalid intervals where `start > end` are skipped (treated as empty/non-existent).
Return the union as a list of `[start, end]` pairs sorted by start.
Constraints
- Each input list is sorted by start in non-decreasing order.
- Intervals within a single list are non-overlapping.
- Intervals are closed: [start, end] includes both endpoints, so touching intervals merge.
- Either list may be empty.
- An interval with start > end is invalid and is skipped (treated as empty).
Examples
Input: ([[1, 3], [5, 7]], [[2, 4], [6, 8]])
Expected Output: [[1, 4], [5, 8]]
Explanation: Interleaving the lists by start: [1,3] then [2,4] overlap into [1,4]; [5,7] then [6,8] overlap into [5,8].
Input: ([[1, 3]], [[3, 5]])
Expected Output: [[1, 5]]
Explanation: Touching closed intervals share the point 3, so [1,3] and [3,5] merge into [1,5].
Hints
- Use two pointers, one per list. At each step advance the pointer whose current interval has the smaller start.
- Maintain a running output list. For each candidate interval, decide between extending the last output interval and appending a new one.
- An interval [s, e] overlaps or touches the last output [ps, pe] exactly when s <= pe. In that case set the last end to max(pe, e); otherwise append [s, e].
- Skip any interval where start > end before considering it for merging.