Unified Segment Set — Problem Statement & Solution Guide

HashingEasyMerge Intervals

TimeO(n log n)

SpaceO(n) (output) or O(1) extra if modifying in place

Problem Description

You are provided with a list of time slots, where each slot is defined by a start and end timestamp. Your task is to consolidate these slots into a minimal set of non-overlapping intervals such that the union of the resulting intervals exactly covers the same time range as the original input. Two intervals are considered overlapping if they share any common point in time, including cases where the end of one interval equals the start of another. Return the consolidated list of intervals sorted by their start times.

DSA Pattern Breakdown

"Unified Segment Set"

easy

WHY DOES IT MATTER?

The merge‑interval pattern appears whenever a system must deduplicate ranges—calendar scheduling, memory allocation, firewall rule consolidation, or timeline analytics. Efficiently collapsing overlapping spans prevents redundant work and reduces storage.

OPTIMIZATION CHALLENGE

The key insight is that sorting imposes a total order where only the most recent merged interval can possibly intersect the next one, eliminating the need for pairwise comparisons and collapsing the problem to a linear pass.

REAL-WORLD CONNECTION

Think of a distributed log compaction service: multiple writers may emit overlapping time windows of events. Compaction merges these windows into a single continuous segment, similar to how Kafka or time‑series databases compact overlapping chunks.

In an interview, sort first, then write the merge loop as a simple if/else; avoid trying to modify the original list in place—use a new result array to keep the code clean and avoid index bugs.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(n) (output) or O(1) extra if modifying in place

Core Theory — Why This Approach?

Merging a collection of intervals into a minimal non‑overlapping set is a classic problem that can be solved efficiently by sorting. The naive view—checking each interval against every other—leads to O(n²) time because each pair must be examined for overlap, which quickly becomes infeasible for large n (e.g., millions of time slots in a calendar service). The optimal paradigm leverages the fact that once intervals are ordered by their start points, any overlap can only occur with the most recent merged interval, allowing a single linear scan to combine them. This reduces the problem to O(n log n) dominated by the initial sort, while the merging step itself is O(n) and uses only O(1) extra space beyond the output list.

Interview Questions on This Problem

Q1How would you merge a list of possibly overlapping time intervals and guarantee the result is the smallest possible set of disjoint intervals?

Sort the intervals by start time, then iterate maintaining a current merged interval. If the next interval's start is ≤ current end, extend the end to max(current end, next end); otherwise, push the current interval to the result and start a new one. This yields a minimal, non‑overlapping set in O(n log n) time.

Q2Can you modify the merging algorithm to also count the total length of the union of intervals without storing the merged list?

Yes. While scanning the sorted intervals, keep a running total. When intervals overlap, only extend the current end; when they don't, add (current end - current start) to the total and reset the current interval. This computes the union length in O(n log n) time and O(1) extra space.

Q3What edge cases must you handle when intervals are given as closed vs. half‑open ranges, and how does that affect the overlap condition?

For closed intervals [a,b] and [c,d], they overlap if c ≤ b. For half‑open [a,b) and [c,d), they overlap if c < b. The algorithm’s condition must be adjusted accordingly; otherwise, adjacent intervals may be incorrectly merged or left separate.

Examples

Example 1

Input

intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

Output

[[1, 6], [8, 10], [15, 18]]

Explanation: Sort intervals by start time: [[1, 3], [2, 6], [8, 10], [15, 18]]. Initialize result with [1, 3]. Next interval [2, 6] overlaps with [1, 3] since 2 <= 3, so merge to [1, 6]. Next interval [8, 10] does not overlap with [1, 6] since 8 > 6, so add [8, 10]. Next interval [15, 18] does not overlap with [8, 10] since 15 > 10, so add [15, 18]. Final result: [[1, 6], [8, 10], [15, 18]].

Example 2

Input

intervals = [[1, 4], [4, 5]]

Output

[[1, 5]]

Explanation: Sort intervals by start time: [[1, 4], [4, 5]]. Initialize result with [1, 4]. Next interval [4, 5] overlaps with [1, 4] since 4 <= 4 (touching endpoints count as overlap), so merge to [1, 5]. Final result: [[1, 5]].

Example 3

Input

intervals = [[5, 6], [1, 2]]

Output

[[1, 2], [5, 6]]

Explanation: Sort intervals by start time: [[1, 2], [5, 6]]. Initialize result with [1, 2]. Next interval [5, 6] does not overlap with [1, 2] since 5 > 2, so add [5, 6]. Final result: [[1, 2], [5, 6]].

Example 4

Input

intervals = [[1, 10], [2, 3], [4, 5]]

Output

[[1, 10]]

Explanation: Sort intervals by start time: [[1, 10], [2, 3], [4, 5]]. Initialize result with [1, 10]. Next interval [2, 3] overlaps with [1, 10] since 2 <= 10, so merge to [1, 10] (end remains 10). Next interval [4, 5] overlaps with [1, 10] since 4 <= 10, so merge to [1, 10] (end remains 10). Final result: [[1, 10]].

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 10^4

Optimal Approach & Strategy

Sort intervals by start time and then merge in one linear scan, achieving O(n log n) time overall.

Brute Force Approach

Compare every interval with every other to detect overlaps and repeatedly merge them until no overlaps remain, leading to O(n²) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (intervals.length === 0) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [];
    let current = [...intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= current[1]) {
            current[1] = Math.max(current[1], intervals[i][1]);
        } else {
            merged.push(current);
            current = [...intervals[i]];
        }
    }
    merged.push(current);
    return merged;
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        vector<int> current = intervals[0];
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] <= current[1]) {
                current[1] = max(current[1], intervals[i][1]);
            } else {
                merged.push_back(current);
                current = intervals[i];
            }
        }
        merged.push_back(current);
        return merged;
    }
};

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][2];
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> merged = new ArrayList<>();
        int[] current = intervals[0].clone();
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= current[1]) {
                current[1] = Math.max(current[1], intervals[i][1]);
            } else {
                merged.add(current);
                current = intervals[i].clone();
            }
        }
        merged.add(current);
        return merged.toArray(new int[merged.size()][2]);
    }
}

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        intervals.sort(key=lambda x: x[0])
        merged = []
        current = intervals[0][:]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= current[1]:
                current[1] = max(current[1], intervals[i][1])
            else:
                merged.append(current)
                current = intervals[i][:]
        merged.append(current)
        return merged

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (intervals.length === 0) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [];
    let current = [...intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= current[1]) {
            current[1] = Math.max(current[1], intervals[i][1]);
        } else {
            merged.push(current);
            current = [...intervals[i]];
        }
    }
    merged.push(current);
    return merged;
};

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Unified Segment Set Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Unified Segment Set — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor