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.length === 0) return [];
  
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [[sorted[0][0], sorted[0][1]]];
  
  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const current = sorted[i];
    
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push([current[0], current[1]]);
    }
  }
  
  return merged;
}
```

The user wants an ES module `solution.js` that exports a function `mergeIntervals(intervals)`.
The function takes an array of `[start, end]` pairs.
It should merge overlapping intervals, including those that touch.
The result should be sorted by start.
It should not mutate the input.
Empty input returns `[]`.

Algorithm:
1. Handle empty input: if `intervals.length === 0`, return `[]`.
2. Create a copy of the input array to avoid mutation.
3. Sort the copied array by the start value of each interval.
4. Initialize a result array with the first interval from the sorted array.
5. Iterate through the rest of the sorted intervals:
   - Let `last` be the last interval in the result array.
   - Let `current` be the interval from the sorted array.
   - If `current[0] <= last[1]`, they overlap or touch. Merge them by updating `last[1]` to `Math.max(last[1], current[1])`.
   - Otherwise, push `current` to the result array.
6. Return the result array.

Let's trace with examples:
`[[1, 4], [2, 5]]` -> sorted: `[[1, 4], [2, 5]]`
result: `[[1, 4]]`
current: `[2, 5]`, `2 <= 4` -> merge: `last[1] = max(4, 5) = 5` -> result: `[[1, 5]]`
Returns `[[1, 5]]`. Correct.

`[[3, 5], [1, 2]]` -> sorted: `[[1, 2], [3, 5]]`
result: `[[1, 2]]`
current: `[3, 5]`, `3 <= 2` is false -> push `[3, 5]` -> result: `[[1, 2], [3, 5]]`
Returns `[[1, 2], [3, 5]]`. Correct.

`[[1, 3], [3, 5]]` -> sorted: `[[1, 3], [3, 5]]`
result: `[[1, 3]]`
current: `[3, 5]`, `3 <= 3` -> merge: `last[1] = max(3, 5) = 5` -> result: `[[1, 5]]`
Returns `[[1, 5]]`. Correct.

`[[1, 10], [2, 3], [4, 8]]` -> sorted: `[[1, 10], [2, 3], [4, 8]]`
result: `[[1, 10]]`
current: `[2, 3]`, `2 <= 10` -> merge: `last[1] = max(10, 3) = 10` -> result: `[[1, 10]]`
current: `[4, 8]`, `4 <= 10` -> merge: `last[1] = max(10, 8) = 10` -> result: `[[1, 10]]`
Returns `[[1, 10]]`. Correct.

Edge cases:
- Empty array: handled.
- Single interval: handled.
- Duplicates: handled by sorting and merging logic.
- Negative numbers: handled by comparison logic.
- Intervals with `start === end`: handled.

Implementation details:
- Use `[...intervals]` to copy.
- Sort with `(a, b) => a[0] - b[0]`.
- Iterate and merge.
- Return new array.

Code structure:
```js
export function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [sorted[0]];
  
  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const current = sorted[i];
    
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
  }
  
  return merged;
}
```

Wait, `last[1] = Math.max(last[1], current[1]);` mutates the array inside `merged`, but `merged` contains references to the original interval arrays from `sorted`. Since `sorted` is a shallow copy of `intervals`, the inner arrays are still references to the original intervals. The problem says "Do not mutate the input array." Mutating the inner arrays might be considered mutating the input. To be strictly safe, I should create new arrays for the merged intervals, or at least ensure I don't mutate the original inner arrays.

Let's adjust to avoid mutating original inner arrays:
```js
export function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [[sorted[0][0], sorted[0][1]]];
  
  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const current = sorted[i];
    
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push([current[0], current[1]]);
    }
  }
  
  return merged;
}
```
This creates new arrays for each interval in `merged`, so the original `intervals` and its inner arrays are untouched. This is safer.

Let's double check constraints and requirements.
- "Do not mutate the input array." -> Usually means the outer array, but avoiding inner mutation is best practice.
- "return a new array of merged intervals sorted ascending by start." -> Handled.
- ES module export -> `export function mergeIntervals(intervals) { ... }`

One minor point: `sorted` contains references to original intervals. When we do `merged.push([current[0], current[1]])`, we create a new array. That's fine.
What about `last[1] = Math.max(...)`? `last` is a new array we created, so mutating it is fine.

Let's test mentally with `[[1, 4], [2, 5]]`:
`sorted` = `[[1, 4], [2, 5]]` (references to original)
`merged` = `[[1, 4]]` (new array)
`i=1`: `current` = `[2, 5]`, `last` = `[1, 4]`
`2 <= 4` -> `last[1] = 5` -> `merged` = `[[1, 5]]`
Returns `[[1, 5]]`. Original `intervals` untouched. Correct.

What if `intervals` has non-array elements? The problem says "array of [start, end] pairs of numbers", so we can assume valid input.

Complexity: Sorting takes O(N log N). Iteration takes O(N). Space O(N) for the copy and result. This is optimal.

One detail: `sorted` array creation `[...intervals]` creates a shallow copy. Sorting it in-place is fine since it's a copy.
The code looks solid.

Let's write it out carefully.

```js
export function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [[sorted[0][0], sorted[0][1]]];
  
  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const current = sorted[i];
    
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push([current[0], current[1]]);
    }
  }
  
  return merged;
}
```

Check edge case: `intervals` with one element `[[1, 2]]`.
`sorted` = `[[1, 2]]`
`merged` = `[[1, 2]]`
Loop doesn't run. Returns `[[1, 2]]`. Correct.

Check edge case: `intervals` with duplicates `[[1, 3], [1, 3]]`.
`sorted` = `[[1, 3], [1, 3]]`
`merged` = `[[1, 3]]`
`i=1`: `current` = `[1, 3]`, `last` = `[1, 3]`
`1 <= 3` -> `last[1] = max(3, 3) = 3`
Returns `[[1, 3]]`. Correct.

Check edge case: `intervals` with containment `[[1, 10], [2, 3]]`.
`sorted` = `[[1, 10], [2, 3]]`
`merged` = `[[1, 10]]`
`i=1`: `current` = `[2, 3]`, `last` = `[1, 10]`
`2 <= 10` -> `last[1] = max(10, 3) = 10`
Returns `[[1, 10]]`. Correct.

All good.

One minor consideration: The problem says "Do not mutate the input array." It doesn't explicitly forbid mutating the inner arrays, but it's safer not to. My solution creates new arrays for the result, so it's fully non-mutating.

I will produce the final code.
No extra fluff.
File name: `solution.js`
Export: `export function mergeIntervals(intervals) { ... }`

Code matches requirements.
Ready. 
I'll format it properly.
One thing: `sorted` might be empty if `intervals` is empty, but I handle that at the top.
The sort comparator `(a, b) => a[0] - b[0]` works for numbers.
All good.
Output matches request.
Proceed. 
Let's generate the response. 
I will wrap it in the requested format.
```js
export function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const merged = [[sorted[0][0], sorted[0][1]]];
  
  for (let i = 1; i < sorted.length; i++) {
    const last = merged[merged.length - 1];
    const current = sorted[i];
    
    if (current[0] <= last[1]) {
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push([current[0], current[1]]);
    }
  }
  
  return merged;
}
```
Looks solid.
I will output this exactly.
No extra text.
Done. 
Self-Correction/Verification during thought:
Is there any case where `a[0] - b[0]` could be problematic? Only if values are huge numbers causing precision loss, but typically intervals are standard numbers. The problem says "numbers", so standard JS numbers. It's fine.
What about `intervals` containing non-finite numbers? Not specified, assume valid.
The code is standard and robust.
Proceeds. 
Output matches. 
Done. 
[Output Generation] -> *Proceeds*