js-02-merge-intervals

# Merge overlapping intervals

Implement an ES module **`solution.js`** exporting a single function:

```js
export function mergeIntervals(intervals) { /* ... */ }
```

`intervals` is an array of `[start, end]` pairs of numbers, each a **closed** interval with
`start <= end`. Merge all overlapping intervals and return a new array of merged intervals
**sorted ascending by start**.

Rules:
- Intervals that **touch** are merged: `[1, 3]` and `[3, 5]` become `[1, 5]`.
- A merged interval's end is the **maximum** end of the intervals that went into it (handle full
  containment, e.g. `[1, 10]` swallows `[2, 3]`).
- The input may be in any order and may contain duplicates. Do **not** mutate the input array.
- An empty input returns `[]`.

Examples:
```js
mergeIntervals([[1, 4], [2, 5]])            // => [[1, 5]]
mergeIntervals([[3, 5], [1, 2]])            // => [[1, 2], [3, 5]]
mergeIntervals([[1, 3], [3, 5]])            // => [[1, 5]]
mergeIntervals([[1, 10], [2, 3], [4, 8]])   // => [[1, 10]]
mergeIntervals([])                          // => []
```

import { test } from "node:test";
import { strict as assert } from "node:assert";
import { mergeIntervals } from "./solution.js";

test("empty input returns empty array", () => {
  assert.deepEqual(mergeIntervals([]), []);
});

test("single interval is returned unchanged", () => {
  assert.deepEqual(mergeIntervals([[1, 3]]), [[1, 3]]);
});

test("unsorted disjoint input is sorted", () => {
  assert.deepEqual(mergeIntervals([[3, 5], [1, 2]]), [[1, 2], [3, 5]]);
});

test("overlapping intervals merge", () => {
  assert.deepEqual(mergeIntervals([[1, 4], [2, 5]]), [[1, 5]]);
});

test("touching endpoints merge", () => {
  assert.deepEqual(mergeIntervals([[1, 3], [3, 5]]), [[1, 5]]);
});

test("containment keeps the wider interval", () => {
  assert.deepEqual(mergeIntervals([[1, 10], [2, 3], [4, 8]]), [[1, 10]]);
});

test("disjoint intervals are left separate", () => {
  assert.deepEqual(mergeIntervals([[1, 2], [4, 5]]), [[1, 2], [4, 5]]);
});

test("duplicates collapse to one", () => {
  assert.deepEqual(mergeIntervals([[1, 2], [1, 2]]), [[1, 2]]);
});

test("mixed unsorted overlapping and disjoint", () => {
  assert.deepEqual(
    mergeIntervals([[8, 10], [1, 3], [2, 6], [15, 18]]),
    [[1, 6], [8, 10], [15, 18]],
  );
});

test("the input array is not mutated", () => {
  const input = [[3, 5], [1, 2]];
  mergeIntervals(input);
  assert.deepEqual(input, [[3, 5], [1, 2]]);
});

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```js
export function mergeIntervals(intervals) {
  if (!intervals || intervals.length === 0) {
    return [];
  }

  // Create a sorted copy to avoid mutating the input
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);

  const result = [];
  let currentStart = sorted[0][0];
  let currentEnd = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];

    // Intervals overlap or touch if start <= currentEnd
    if (start <= currentEnd) {
      currentEnd = Math.max(currentEnd, end);
    } else {
      result.push([currentStart, currentEnd]);
      currentStart = start;
      currentEnd = end;
    }
  }

  // Push the final merged interval
  result.push([currentStart, currentEnd]);

  return result;
}
```

The task is to implement a function that merges overlapping intervals. Let me break down the requirements:

1. Input: array of [start, end] pairs of numbers
2. Output: new array of merged intervals sorted by start
3. Intervals that touch (end of one equals start of another) should be merged
4. Merged interval's end is the maximum end of all overlapping intervals
5. Don't mutate the input array
6. Empty input returns []

The algorithm:
1. If input is empty, return []
2. Sort intervals by start time
3. Iterate through sorted intervals and merge overlapping ones
4. Two intervals overlap if the current interval's start <= previous interval's end (considering they touch)
5. When merging, update the end to be the maximum of both ends

Let me write the solution:

```js
export function mergeIntervals(intervals) {
  if (!intervals || intervals.length === 0) {
    return [];
  }
  
  // Create a copy to avoid mutating input
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  
  const result = [];
  let currentStart = sorted[0][0];
  let currentEnd = sorted[0][1];
  
  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    
    // Check if current interval overlaps with or touches the previous one
    if (start <= currentEnd) {
      // Merge by extending the end if needed
      currentEnd = Math.max(currentEnd, end);
    } else {
      // No overlap, push the current merged interval and start a new one
      result.push([currentStart, currentEnd]);
      currentStart = start;
      currentEnd = end;
    }
  }
  
  // Push the last interval
  result.push([currentStart, currentEnd]);
  
  return result;
}
```

I'm verifying the logic with a few test cases. The algorithm handles different scenarios of interval merging correctly. When intervals touch or overlap, they get combined into a single interval. The sorting ensures we process intervals in order, and the merging logic captures the maximum end point.

The implementation covers edge cases like empty arrays, single intervals, and multiple overlapping intervals. It creates a new array without modifying the original input.