Crack the Backend

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all intervals in the input. Two intervals overlap if one starts before the other ends (e.g. [1,3] and [2,6] overlap). Merge by taking the union: [min(starts), max(ends)].

Key Observations

Sort by start: After sorting by start, overlapping intervals will be consecutive. We maintain a result list. For each interval: if the result is empty or the current interval's start is greater than the last interval's end, there is no overlap — add the current as a new interval. Otherwise the current overlaps the last — update the last interval's end to max(last.end, current.end).
This greedy works because after sorting, any interval that could merge with the current one would already be in the "last" merged block.

Approach

High-level: Sort intervals by start. For each interval: if result is empty or interval.start > result.last().end, append new interval; else set result.last().end = max(result.last().end, interval.end). Return result.

Steps: Arrays.sort(intervals, (a,b)->a[0]-b[0]). List result. For each int[] i: if result.isEmpty() || result.get(last)[1] < i[0], result.add(i.clone()); else result.get(last)[1] = max(result.get(last)[1], i[1]). Return result.

Implementation

Java

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a,b) -> a[0]-b[0]);
    List<int[]> list = new ArrayList<>();

    for (int[] i : intervals) {
        if (list.isEmpty() || list.get(list.size()-1)[1] < i[0]) {
            list.add(i.clone());
        }
        else {
            list.get(list.size()-1)[1] = Math.max(list.get(list.size()-1)[1], i[1]);
        }
    }

    return list.toArray(int[][]::new);
}

Test Cases

Example 1

Input

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

Expected

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

Explanation

[1,3] and [2,6] merge to [1,6].

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.