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 Meta.

What role is this question designed for?

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

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].

Input: ([], [])

Expected Output: []

Explanation: Both inputs empty: the union is empty.

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

Expected Output: [[1, 10]]

Explanation: [1,10] fully contains [2,3] and [4,5], so the union is just [1,10].

Input: ([[1, 2], [5, 6]], [])

Expected Output: [[1, 2], [5, 6]]

Explanation: One empty list: the result is the other list, already minimal and sorted.

Input: ([[1, 2]], [[4, 3], [5, 6]])

Expected Output: [[1, 2], [5, 6]]

Explanation: The interval [4,3] is invalid (start > end) and is skipped; [1,2] and [5,6] do not overlap.

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

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

Explanation: [1,4] and [2,5] overlap into [1,5]; [6,8] stands alone; [9,10] is a non-overlapping tail.

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.

Quick Overview

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.