> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/medium/56.-merge-intervals.md).

# 56. Merge Intervals

## Intitution

When intervals are unsorted, it’s hard to find overlaps. But if we sort all intervals by their **start time**, then we can easily compare each interval with the one before it to check for overlap.

If two intervals overlap, we can **merge them** by taking the earliest start and the latest end of the two. This way, we progressively build merged intervals while ensuring there are no overlaps in the final result.

## Complexity

| Space Complexity | Time Complexity            |
| ---------------- | -------------------------- |
| $$\text{O}(1)$$  | $$\text{O}(n + n\log(n))$$ |

## Code

```java
public int[][] merge(int[][] intervals) {
    // Step 1: Sort intervals by their start time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    // List to hold merged non-overlapping intervals
    List<int[]> mergedIntervals = new ArrayList<>();

    // Step 2: Start with the first interval as the previous one
    int[] previousInterval = intervals[0];

    // Step 3: Traverse remaining intervals
    for (int i = 1; i < intervals.length; ++i) {
        int[] currentInterval = intervals[i];

        // Step 4: If there's an overlap, merge current with previous
        if (currentInterval[0] <= previousInterval[1]) {
            // Extend the current interval to include the previous one
            currentInterval[0] = Math.min(currentInterval[0], previousInterval[0]);
            currentInterval[1] = Math.max(currentInterval[1], previousInterval[1]);
        } else {
            // No overlap: add the previous interval to the result
            mergedIntervals.add(previousInterval);
        }

        // Update previous to be the (possibly merged) current
        previousInterval = currentInterval;
    }

    // Step 5: Add the last interval
    mergedIntervals.add(previousInterval);

    // Step 6: Convert the result list to a 2D array
    int[][] result = new int[mergedIntervals.size()][2];
    for (int i = 0; i < mergedIntervals.size(); ++i) {
        result[i] = mergedIntervals.get(i);
    }

    return result;
}

```