Merge Intervals in Python
2 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when each one starts no later than the other ends: a[0] <= b[1] and b[0] <= a[1]. Search the list for any such pair, replace it with one interval from the smaller start to the larger end, and search again from the beginning, because the bigger interval may now reach a neighbour it did not reach before. When a full search finds nothing, sort what is left.
def merge(intervals: list[list[int]]) -> list[list[int]]:
result = [list(iv) for iv in intervals]
merged_one = True
while merged_one:
merged_one = False
for i in range(len(result)):
for j in range(i + 1, len(result)):
a, b = result[i], result[j]
if a[0] <= b[1] and b[0] <= a[1]: # overlap or touch
result[i] = [min(a[0], b[0]), max(a[1], b[1])]
del result[j]
merged_one = True
break
if merged_one:
break # the list changed, so start the search over
return sorted(result)
Sort the intervals by start. Now walk them in order and keep a merged list. If the current interval starts at or before the end of the last merged one, it overlaps, so stretch that end to whichever end is larger. Otherwise there is a gap, and since every later interval starts even further right, nothing after it can reach back across that gap: append the current interval as a new one.
def merge(intervals: list[list[int]]) -> list[list[int]]:
merged: list[list[int]] = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]: # overlaps or touches the last one
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
Merge Intervals in JavaScript
2 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.
Ranges a and b overlap exactly when a[0] <= b[1] && b[0] <= a[1]: neither one finishes before the other begins. Work on a copy built with map, compare every pair, and on the first hit replace a with the combined range and splice out b. A labelled break search leaves both loops at once, and the outer while runs the scan again from the top, since the wider range might now reach a pair it missed before. When a full scan changes nothing, sort the leftovers by start.
function merge(intervals) {
const result = intervals.map(([start, end]) => [start, end]);
let changed = true;
while (changed) {
changed = false;
search: for (let i = 0; i < result.length; i++) {
for (let j = i + 1; j < result.length; j++) {
const a = result[i];
const b = result[j];
if (a[0] <= b[1] && b[0] <= a[1]) {
// they overlap or touch: fold b into a and drop b
result[i] = [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
result.splice(j, 1);
changed = true;
break search;
}
}
}
}
return result.sort((x, y) => x[0] - y[0]);
}
toSorted hands back a new outer array ordered by the comparator (a, b) => a[0] - b[0], so the caller's order survives. Destructure each pair in a for...of loop and look at merged.at(-1), which is undefined while merged is empty. When the current start is not past that range's end, the two belong together and the end grows to the bigger of the two. Otherwise a gap has opened, and because every later pair starts further right, no later pair can bridge it: push a new [start, end].
function merge(intervals) {
const merged = [];
for (const [start, end] of intervals.toSorted((a, b) => a[0] - b[0])) {
const last = merged.at(-1);
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end); // overlaps or touches the last one
} else {
merged.push([start, end]);
}
}
return merged;
}
Merge Intervals in TypeScript
2 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.
Two ranges a and b overlap when neither ends before the other starts: a[0] <= b[1] && b[0] <= a[1]. Copy every pair into a fresh number[][], then scan all pairs. On the first hit, put the combined range at i, splice out j and restart the scan, since the wider range may now reach a neighbour it missed. When a full scan merges nothing, sort what is left by start.
function merge(intervals: number[][]): number[][] {
const result: number[][] = intervals.map(([start, end]) => [start, end]);
let changed = true;
while (changed) {
changed = false;
search: for (let i = 0; i < result.length; i++) {
for (let j = i + 1; j < result.length; j++) {
const a = result[i];
const b = result[j];
if (a[0] <= b[1] && b[0] <= a[1]) {
// they overlap or touch: fold b into a and drop b
result[i] = [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
result.splice(j, 1);
changed = true;
break search;
}
}
}
}
return result.sort((x, y) => (x[0] < y[0] ? -1 : x[0] > y[0] ? 1 : 0));
}
Spread the input into a new array and sort that copy by start, so the caller's order stays put. Walk it once with a merged list: if the current start is at or before the last merged end, raise that end with Math.max; otherwise a gap has opened that no later range can close, because every later range starts further right, so push a fresh [start, end]. Pushing a new pair instead of the input's own array keeps the end updates off the caller's data.
function merge(intervals: number[][]): number[][] {
const sorted = [...intervals].sort((a, b) => (a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0));
const merged: number[][] = [];
for (const [start, end] of sorted) {
const last = merged[merged.length - 1];
if (last !== undefined && start <= last[1]) {
last[1] = Math.max(last[1], end); // overlaps or touches the last one
} else {
merged.push([start, end]);
}
}
return merged;
}
Merge Intervals in Java
2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.
Rows a and b intersect exactly when a[0] <= b[1] && b[0] <= a[1]. The method copies each row into an ArrayList<int[]>, since it needs a collection that can shrink and a Java array has a fixed length. A while loop then runs passes over the list. On the first intersecting pair it stores a new combined row with result.set(i, …), drops the other with result.remove(j), flips mergedOne, and the labeled break search exits both for loops so the next pass begins again at index 0. A pass that leaves mergedOne false ends the loop, and the list is sorted and turned back into an array.
import java.util.*;
public class Main {
static int[][] merge(int[][] intervals) {
List<int[]> result = new ArrayList<>();
for (int[] iv : intervals) {
result.add(iv.clone()); // own copy, so the caller's arrays stay as they are
}
boolean mergedOne = true;
while (mergedOne) {
mergedOne = false;
search:
for (int i = 0; i < result.size(); i++) {
for (int j = i + 1; j < result.size(); j++) {
int[] a = result.get(i);
int[] b = result.get(j);
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap or touch
result.set(i, new int[] {Math.min(a[0], b[0]), Math.max(a[1], b[1])});
result.remove(j);
mergedOne = true;
break search; // the list changed, so start the search over
}
}
}
}
result.sort(Comparator.comparingInt(a -> a[0]));
return result.toArray(new int[0][]);
}
}
Begin with intervals.clone(), because Arrays.sort rearranges whatever array it receives, and order that copy by first column with Comparator.comparingInt. Then iterate, collecting output rows in an ArrayList<int[]>. The row under construction is merged.getLast(), a method List gained in Java 21. If the current row starts no later than that row's end, Math.max raises the end. If it starts beyond it, a gap has opened that no later row can close, since every later row starts further right, so a fresh new int[] {iv[0], iv[1]} joins the list. Since the cloned outer array still points at the caller's rows, that fresh int[] is what keeps the getLast()[1] write away from the caller's data.
import java.util.*;
public class Main {
static int[][] merge(int[][] intervals) {
int[][] sorted = intervals.clone(); // Arrays.sort works in place; keep the caller's order
Arrays.sort(sorted, Comparator.comparingInt(a -> a[0]));
List<int[]> merged = new ArrayList<>();
for (int[] iv : sorted) {
if (!merged.isEmpty() && iv[0] <= merged.getLast()[1]) { // overlaps or touches the last one
merged.getLast()[1] = Math.max(merged.getLast()[1], iv[1]);
} else {
merged.add(new int[] {iv[0], iv[1]}); // a fresh pair, not the caller's array
}
}
return merged.toArray(new int[0][]);
}
}
Merge Intervals in Go
2 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.
The test for two pairs a and b is a[0] <= b[1] && b[0] <= a[1]: neither one finishes before the other begins. The function copies every pair into its own []int, tries every index pair i < j, and on the first hit overwrites result[i] with the combined range (the built-in min and max) and cuts result[j] out with slices.Delete. The slice is now shorter and the widened pair may touch something it missed before, so the labelled continue search abandons both inner loops and begins a fresh pass. A pass with no hit falls through to break, and the survivors get sorted by left end.
package main
import (
"cmp"
"slices"
)
func merge(intervals [][]int) [][]int {
result := make([][]int, 0, len(intervals))
for _, iv := range intervals {
result = append(result, []int{iv[0], iv[1]}) // own copy, so the caller's pairs stay as they are
}
search:
for {
for i := range result {
for j := i + 1; j < len(result); j++ {
a, b := result[i], result[j]
if a[0] <= b[1] && b[0] <= a[1] { // overlap or touch
result[i] = []int{min(a[0], b[0]), max(a[1], b[1])}
result = slices.Delete(result, j, j+1)
continue search // the slice changed, so start the search over
}
}
}
break // a full search found nothing to merge
}
slices.SortFunc(result, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })
return result
}
slices.SortFunc reorders the slice it is given, so the function sorts a slices.Clone, comparing left ends with cmp.Compare. It then ranges over that copy with merged declared as a nil slice, which append grows with no setup. The if n := len(merged); n > 0 && … form names the length and guards the empty case in one statement. When the current pair begins at or before merged[n-1][1], the built-in max raises that right end. When it begins further right, a gap has opened that no later pair can bridge, since each of them begins later still, so a fresh []int is appended as a new range: the clone shares its inner slices with the caller, and the fresh pair keeps the later write away from the caller's data.
package main
import (
"cmp"
"slices"
)
func merge(intervals [][]int) [][]int {
sorted := slices.Clone(intervals) // SortFunc sorts in place; keep the caller's order
slices.SortFunc(sorted, func(a, b []int) int { return cmp.Compare(a[0], b[0]) })
var merged [][]int
for _, iv := range sorted {
if n := len(merged); n > 0 && iv[0] <= merged[n-1][1] { // overlaps or touches the last one
merged[n-1][1] = max(merged[n-1][1], iv[1])
} else {
merged = append(merged, []int{iv[0], iv[1]}) // a fresh pair, not the caller's slice
}
}
return merged
}
Merge Intervals in C#
2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.
Rows a and b overlap exactly when a[0] <= b[1] && b[0] <= a[1]. The method copies every row into a List<int[]>, because the list has to shrink as pairs collapse and a C# array cannot. A while loop makes passes over the list: the first overlapping pair is replaced in place with one row from the smaller start to the larger end, the partner is removed with RemoveAt, and mergedOne flips. C# has no labeled break, so the inner break leaves only the inner loop and the && !mergedOne in the outer loop's condition stops that one, which starts the next pass at index 0. A pass that merges nothing ends the loop; the leftovers are then sorted by start with OrderBy.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[][] Merge(int[][] intervals)
{
var result = new List<int[]>();
foreach (var iv in intervals)
{
result.Add(new[] { iv[0], iv[1] }); // own copy, so the caller's rows stay as they are
}
bool mergedOne = true;
while (mergedOne)
{
mergedOne = false;
for (int i = 0; i < result.Count && !mergedOne; i++)
{
for (int j = i + 1; j < result.Count; j++)
{
int[] a = result[i], b = result[j];
if (a[0] <= b[1] && b[0] <= a[1]) // overlap or touch
{
result[i] = new[] { Math.Min(a[0], b[0]), Math.Max(a[1], b[1]) };
result.RemoveAt(j);
mergedOne = true;
break; // the list changed, so start the search over
}
}
}
}
return result.OrderBy(iv => iv[0]).ToArray();
}
}
OrderBy(iv => iv[0]) yields the rows in start order without touching the caller's array, and it compares the keys with Comparer<int>.Default rather than subtracting them, which matters once starts sit near ±2×10⁹. Walk the sorted rows and keep a List<int[]> of output. When the current row starts no later than the end of the last row built, it overlaps or touches, so Math.Max raises that end. When it starts beyond it, a gap has opened that no later row can close, since every later row starts further right, and a fresh new[] { iv[0], iv[1] } joins the list. That fresh array is what keeps the end-stretching write off the caller's rows.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
public static int[][] Merge(int[][] intervals)
{
var merged = new List<int[]>();
foreach (var iv in intervals.OrderBy(iv => iv[0])) // a sorted copy; the caller's order is untouched
{
if (merged.Count > 0 && iv[0] <= merged[merged.Count - 1][1]) // overlaps or touches the last one
{
merged[merged.Count - 1][1] = Math.Max(merged[merged.Count - 1][1], iv[1]);
}
else
{
merged.Add(new[] { iv[0], iv[1] }); // a fresh pair, not the caller's array
}
}
return merged.ToArray();
}
}
Merge Intervals in C++
2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.
Two rows a and b overlap when a[0] <= b[1] && b[0] <= a[1]. Work on a copy of intervals, test every pair, and on the first hit widen result[i] with min and max, erase row j, and start over: the wider row may now reach one it missed. A bool flag ends both loops at once, since C++ has no labelled break. When a pass merges nothing, sort the rows by start.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result(intervals); // own copy; the caller's rows stay as they are
bool mergedOne = true;
while (mergedOne) {
mergedOne = false;
for (size_t i = 0; i < result.size() && !mergedOne; i++) {
for (size_t j = i + 1; j < result.size(); j++) {
vector<int>& a = result[i];
const vector<int>& b = result[j];
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap or touch
a = {min(a[0], b[0]), max(a[1], b[1])};
result.erase(result.begin() + j);
mergedOne = true; // the vector changed, so start the search over
break;
}
}
}
}
sort(result.begin(), result.end(),
[](const vector<int>& x, const vector<int>& y) { return x[0] < y[0]; });
return result;
}
};
Copy the rows and sort the copy with a lambda that compares starts with <, never by subtracting. Then sweep once: if the current row starts at or before merged.back()[1], raise that end with max; otherwise a gap has opened that no later row can bridge, so push_back the row. reserve sizes the output once, because it can never hold more rows than the input.
#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> sorted(intervals); // sort a copy, not the caller's vector
sort(sorted.begin(), sorted.end(),
[](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
vector<vector<int>> merged;
merged.reserve(sorted.size());
for (const vector<int>& iv : sorted) {
if (!merged.empty() && iv[0] <= merged.back()[1]) { // overlaps or touches the last one
merged.back()[1] = max(merged.back()[1], iv[1]);
} else {
merged.push_back(iv);
}
}
return merged;
}
};
Merge Intervals in C
2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.
Copy every interval into two scratch arrays, lo and hi, so the caller's rows are never written. Test every pair with lo[i] <= hi[j] && lo[j] <= hi[i]; on a hit, widen interval i, move the last interval into slot j, shrink the count and scan again from the start. When a pass merges nothing, order the survivors by start with a small insertion sort and copy each into its own malloc'ed row of two ints.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
/**
* Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
*/
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
*returnColumnSizes = NULL;
if (intervalsSize == 0) return NULL;
int* lo = malloc(intervalsSize * sizeof *lo);
int* hi = malloc(intervalsSize * sizeof *hi);
for (int i = 0; i < intervalsSize; i++) {
lo[i] = intervals[i][0];
hi[i] = intervals[i][1];
}
int count = intervalsSize;
bool mergedOne = true;
while (mergedOne) {
mergedOne = false;
for (int i = 0; i < count && !mergedOne; i++) {
for (int j = i + 1; j < count; j++) {
if (lo[i] <= hi[j] && lo[j] <= hi[i]) { // overlap or touch
if (lo[j] < lo[i]) lo[i] = lo[j];
if (hi[j] > hi[i]) hi[i] = hi[j];
lo[j] = lo[count - 1]; // drop j by moving the last one into its slot
hi[j] = hi[count - 1];
count--;
mergedOne = true; // the set changed, so start the search over
break;
}
}
}
}
for (int i = 1; i < count; i++) { // insertion sort by start, comparing, never subtracting
int l = lo[i], h = hi[i], k = i - 1;
while (k >= 0 && lo[k] > l) {
lo[k + 1] = lo[k];
hi[k + 1] = hi[k];
k--;
}
lo[k + 1] = l;
hi[k + 1] = h;
}
int** result = malloc(count * sizeof *result);
*returnColumnSizes = malloc(count * sizeof **returnColumnSizes);
for (int i = 0; i < count; i++) {
result[i] = malloc(2 * sizeof *result[i]);
result[i][0] = lo[i];
result[i][1] = hi[i];
(*returnColumnSizes)[i] = 2;
}
*returnSize = count;
free(lo);
free(hi);
return result;
}
Copy the row pointers into a malloc'ed array and qsort that, so the caller's array keeps its order and no row is touched. The comparator returns (a > b) - (a < b), which cannot overflow the way a - b does at ±2×10⁹. Then sweep once: a start at or before the last merged end raises that end; anything else opens a new two-int row. The output never has more rows than the input, so size it once up front.
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
static int byStart(const void* x, const void* y) {
int a = (*(int* const*)x)[0];
int b = (*(int* const*)y)[0];
return (a > b) - (a < b); // never a - b: that overflows for starts 4×10⁹ apart
}
/**
* Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
*/
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
*returnColumnSizes = NULL;
if (intervalsSize == 0) return NULL;
int** order = malloc(intervalsSize * sizeof *order); // sort pointers, not the caller's rows
memcpy(order, intervals, intervalsSize * sizeof *order);
qsort(order, intervalsSize, sizeof *order, byStart);
int** result = malloc(intervalsSize * sizeof *result);
int count = 0;
for (int i = 0; i < intervalsSize; i++) {
int start = order[i][0], end = order[i][1];
if (count > 0 && start <= result[count - 1][1]) { // overlaps or touches the last one
if (end > result[count - 1][1]) result[count - 1][1] = end;
} else {
result[count] = malloc(2 * sizeof *result[count]);
result[count][0] = start;
result[count][1] = end;
count++;
}
}
free(order);
*returnColumnSizes = malloc(count * sizeof **returnColumnSizes);
for (int i = 0; i < count; i++) (*returnColumnSizes)[i] = 2;
*returnSize = count;
return result;
}
Merge Intervals in Kotlin
2 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when a[0] <= b[1] && b[0] <= a[1]. Copy every row with copyOf() into a MutableList<IntArray>, because an Array cannot shrink. Each pass looks for the first overlapping pair, replaces it with intArrayOf(minOf(…), maxOf(…)), drops the partner with removeAt(j) and leaves both loops through the labeled break@search, so the next pass starts again at index 0. A pass that merges nothing ends the loop; sortBy { it[0] } and toTypedArray() give the answer.
class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
val result = intervals.mapTo(mutableListOf()) { it.copyOf() } // own copies of the rows
var mergedOne = true
while (mergedOne) {
mergedOne = false
search@ for (i in result.indices) {
for (j in i + 1 until result.size) {
val a = result[i]
val b = result[j]
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap or touch
result[i] = intArrayOf(minOf(a[0], b[0]), maxOf(a[1], b[1]))
result.removeAt(j)
mergedOne = true
break@search // the list changed, so start the search over
}
}
}
}
result.sortBy { it[0] }
return result.toTypedArray()
}
}
intervals.sortedBy { it[0] } returns a new List<IntArray> ordered by start and leaves the caller's array alone. Walk it once, collecting output rows in an ArrayList<IntArray>. lastOrNull() gives the row under construction: if the current row starts at or before its end, maxOf raises that end; otherwise a gap has opened that no later row can close, since every later row starts further right, so a fresh iv.copyOf() joins the list.
class Solution {
fun merge(intervals: Array<IntArray>): Array<IntArray> {
val merged = ArrayList<IntArray>(intervals.size)
for (iv in intervals.sortedBy { it[0] }) {
val last = merged.lastOrNull()
if (last != null && iv[0] <= last[1]) { // overlaps or touches the last one
last[1] = maxOf(last[1], iv[1])
} else {
merged.add(iv.copyOf()) // a fresh row, so the caller's arrays stay as they are
}
}
return merged.toTypedArray()
}
}
Merge Intervals in Rust
2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when a[0] <= b[1] && b[0] <= a[1]. The function owns the Vec<Vec<i32>> it receives, so it edits it directly. Each pass looks for the first overlapping pair, builds the combined interval with min and max, writes it to index i, takes j out with Vec::remove and leaves both loops with break 'search, so the next pass starts again from the front. A pass that merges nothing ends the loop, and sort_unstable_by_key orders what is left by start.
impl Solution {
pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut result = intervals; // we own the Vec, so merge in place
let mut merged_one = true;
while merged_one {
merged_one = false;
'search: for i in 0..result.len() {
for j in i + 1..result.len() {
let (a, b) = (&result[i], &result[j]);
if a[0] <= b[1] && b[0] <= a[1] {
// overlap or touch
let combined = vec![a[0].min(b[0]), a[1].max(b[1])];
result[i] = combined;
result.remove(j);
merged_one = true;
break 'search; // the Vec changed, so start the search over
}
}
}
}
result.sort_unstable_by_key(|iv| iv[0]);
result
}
}
Take intervals as mut and sort it in place with sort_unstable_by_key(|iv| iv[0]). Then move each row into the output in order. merged.last_mut() hands out a &mut Vec<i32> to the row under construction: if the current row starts at or before its end, the match guard lets the first arm raise that end with max. Otherwise a gap has opened that no later row can close, so the row itself is pushed, with no copy, because the loop consumes the Vec.
impl Solution {
pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
intervals.sort_unstable_by_key(|iv| iv[0]);
let mut merged: Vec<Vec<i32>> = Vec::with_capacity(intervals.len());
for iv in intervals {
match merged.last_mut() {
Some(last) if iv[0] <= last[1] => last[1] = last[1].max(iv[1]), // overlaps or touches
_ => merged.push(iv),
}
}
merged
}
}
Merge Intervals in Swift
2 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when a[0] <= b[1] && b[0] <= a[1]. var result = intervals is already a private copy, because Swift arrays are value types. Each pass looks for the first overlapping pair, stores [min(…), max(…)] at index i, drops the partner with remove(at: j) and leaves both loops through the labeled break search, so the next pass starts again at index 0. A pass that merges nothing ends the loop, and sorted(by:) orders what is left by start.
class Solution {
func merge(_ intervals: [[Int]]) -> [[Int]] {
var result = intervals // a value copy; the caller's array is untouched
var mergedOne = true
while mergedOne {
mergedOne = false
search: for i in result.indices {
for j in (i + 1)..<result.count {
let a = result[i], b = result[j]
if a[0] <= b[1] && b[0] <= a[1] { // overlap or touch
result[i] = [min(a[0], b[0]), max(a[1], b[1])]
result.remove(at: j)
mergedOne = true
break search // the array changed, so start the search over
}
}
}
}
return result.sorted { $0[0] < $1[0] }
}
}
intervals.sorted(by: { $0[0] < $1[0] }) returns a new array ordered by start. Walk it once, building merged. if let last = merged.last reads the row under construction: if the current row starts at or before its end, the end is raised in place through merged[merged.count - 1][1], since last is only a copy. Otherwise a gap has opened that no later row can close, because every later row starts further right, so the row is appended as a new interval.
class Solution {
func merge(_ intervals: [[Int]]) -> [[Int]] {
var merged: [[Int]] = []
merged.reserveCapacity(intervals.count)
for iv in intervals.sorted(by: { $0[0] < $1[0] }) {
if let last = merged.last, iv[0] <= last[1] { // overlaps or touches the last one
merged[merged.count - 1][1] = max(last[1], iv[1])
} else {
merged.append(iv)
}
}
return merged
}
}
Merge Intervals in PHP
2 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.
Two intervals $a and $b overlap when $a[0] <= $b[1] && $b[0] <= $a[1]. PHP arrays are copied on assignment, so $result = $intervals is a private working copy. Each pass looks for the first overlapping pair, stores [min(…), max(…)] at index $i, cuts the partner out with array_splice (which renumbers the keys) and leaves both loops with break 2. A pass that merges nothing ends the loop, and usort with <=> orders what is left by start.
<?php
class Solution {
/**
* @param int[][] $intervals
* @return int[][]
*/
function merge(array $intervals): array {
$result = $intervals; // arrays are copied on assignment
$mergedOne = true;
while ($mergedOne) {
$mergedOne = false;
$n = count($result);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
[$a, $b] = [$result[$i], $result[$j]];
if ($a[0] <= $b[1] && $b[0] <= $a[1]) { // overlap or touch
$result[$i] = [min($a[0], $b[0]), max($a[1], $b[1])];
array_splice($result, $j, 1); // remove and renumber the keys
$mergedOne = true;
break 2; // the array changed, so start the search over
}
}
}
}
usort($result, fn(array $x, array $y): int => $x[0] <=> $y[0]);
return $result;
}
}
usort sorts $intervals by start with the spaceship operator <=>; the parameter is already a copy, so the caller's array keeps its order. The foreach destructures each row into [$start, $end]. If the row starts at or before the end of the last merged one, $merged[$last][1] is raised with max; otherwise a gap has opened that no later row can close, so $merged[] = [$start, $end] appends a new interval.
<?php
class Solution {
/**
* @param int[][] $intervals
* @return int[][]
*/
function merge(array $intervals): array {
usort($intervals, fn(array $x, array $y): int => $x[0] <=> $y[0]);
$merged = [];
foreach ($intervals as [$start, $end]) {
$last = count($merged) - 1;
if ($last >= 0 && $start <= $merged[$last][1]) { // overlaps or touches the last one
$merged[$last][1] = max($merged[$last][1], $end);
} else {
$merged[] = [$start, $end];
}
}
return $merged;
}
}
Merge Intervals in Ruby
2 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when a[0] <= b[1] && b[0] <= a[1]. Start from intervals.map(&:dup) so the caller's rows stay untouched. Each pass asks (0...result.size).to_a.combination(2).find for the first overlapping index pair; the enumerator stops at the first hit. delete_at(j) takes the partner out, index i gets the combined [min, max] row, and the loop searches again from the start. When no pair is left, sort_by(&:first) orders the rest.
# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
result = intervals.map(&:dup)
loop do
pair = (0...result.size).to_a.combination(2).find do |i, j|
result[i][0] <= result[j][1] && result[j][0] <= result[i][1] # overlap or touch
end
break unless pair
i, j = pair
a = result[i]
b = result.delete_at(j) # j > i, so index i does not move
result[i] = [[a[0], b[0]].min, [a[1], b[1]].max]
end
result.sort_by(&:first)
end
sort_by(&:first) returns a new array ordered by start, and each_with_object([]) threads the result through the block. The block destructures each row into |(start, finish), merged|. If the row starts at or before merged.last[1], that end is raised in place; otherwise a gap has opened that no later row can close, so a fresh [start, finish] is appended.
# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
intervals.sort_by(&:first).each_with_object([]) do |(start, finish), merged|
if !merged.empty? && start <= merged.last[1] # overlaps or touches the last one
merged.last[1] = [merged.last[1], finish].max
else
merged << [start, finish] # a fresh array, not the caller's row
end
end
end
Merge Intervals in Dart
2 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when a[0] <= b[1] && b[0] <= a[1]. The collection for with a spread, [for (final iv in intervals) [...iv]], copies every row so the caller's lists stay as they are. Each pass looks for the first overlapping pair, stores [min(…), max(…)] from dart:math at index i, drops the partner with removeAt(j) and leaves both loops with the labeled break search. A pass that merges nothing ends the loop, and sort with compareTo orders what is left by start.
import 'dart:math';
class Solution {
List<List<int>> merge(List<List<int>> intervals) {
final result = [for (final iv in intervals) [...iv]]; // own copies of the rows
var mergedOne = true;
while (mergedOne) {
mergedOne = false;
search:
for (var i = 0; i < result.length; i++) {
for (var j = i + 1; j < result.length; j++) {
final a = result[i], b = result[j];
if (a[0] <= b[1] && b[0] <= a[1]) { // overlap or touch
result[i] = [min(a[0], b[0]), max(a[1], b[1])];
result.removeAt(j);
mergedOne = true;
break search; // the list changed, so start the search over
}
}
}
}
result.sort((x, y) => x[0].compareTo(y[0]));
return result;
}
}
[...intervals]..sort((a, b) => a[0].compareTo(b[0])) copies the outer list and sorts the copy by start in one expression, thanks to the cascade ... Walk it once, building merged. If the current row starts at or before merged.last[1], that end is raised in place with max; otherwise a gap has opened that no later row can close, so a fresh [iv[0], iv[1]] is added.
import 'dart:math';
class Solution {
List<List<int>> merge(List<List<int>> intervals) {
final sorted = [...intervals]..sort((a, b) => a[0].compareTo(b[0]));
final merged = <List<int>>[];
for (final iv in sorted) {
if (merged.isNotEmpty && iv[0] <= merged.last[1]) { // overlaps or touches the last one
merged.last[1] = max(merged.last[1], iv[1]);
} else {
merged.add([iv[0], iv[1]]); // a fresh list, not the caller's row
}
}
return merged;
}
}
Merge Intervals in Scala
2 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.
Two intervals a and b overlap when a(0) <= b(1) && b(0) <= a(1). The rows are cloned into a mutable.ArrayBuffer, because an Array cannot shrink. The helper overlappingPair scans every pair inside boundary and leaves the for with break(Some((i, j))) at the first overlap, which avoids a return from inside the loop's closure. The main loop replaces row i with Array(a(0) min b(0), a(1) max b(1)), removes row j, and asks again until the helper returns None; sortBy(_(0)) orders the rest.
import scala.collection.mutable.ArrayBuffer
import scala.util.boundary, boundary.break
object Solution {
def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
val result = ArrayBuffer.from(intervals.map(_.clone())) // own copies of the rows
var searching = true
while (searching) {
overlappingPair(result) match {
case Some((i, j)) =>
val (a, b) = (result(i), result(j))
result(i) = Array(a(0) min b(0), a(1) max b(1))
result.remove(j) // j > i, so index i does not move
case None => searching = false
}
}
result.sortBy(_(0)).toArray
}
// The first pair of indices whose intervals overlap or touch, if any.
private def overlappingPair(xs: ArrayBuffer[Array[Int]]): Option[(Int, Int)] = boundary {
for (i <- xs.indices; j <- i + 1 until xs.length) {
if (xs(i)(0) <= xs(j)(1) && xs(j)(0) <= xs(i)(1)) break(Some((i, j)))
}
None
}
}
intervals.sortBy(_(0)) returns a new array ordered by start, using the Ordering[Int] to compare. Walk it once, building a mutable.ArrayBuffer[Array[Int]]. If the current row starts at or before the end of merged.last, that end is raised in place with max; otherwise a gap has opened that no later row can close, so a fresh Array(iv(0), iv(1)) is appended. toArray gives the answer.
import scala.collection.mutable.ArrayBuffer
object Solution {
def merge(intervals: Array[Array[Int]]): Array[Array[Int]] = {
val merged = ArrayBuffer.empty[Array[Int]]
for (iv <- intervals.sortBy(_(0))) {
if (merged.nonEmpty && iv(0) <= merged.last(1)) { // overlaps or touches the last one
val last = merged.last
last(1) = last(1) max iv(1)
} else {
merged += Array(iv(0), iv(1)) // a fresh row, not the caller's array
}
}
merged.toArray
}
}
FAQ for Python
How do I insert one new interval into a list that is already merged?
The quick way is to append it and call merge again, which costs O(n log n). Because the list is already sorted and has no overlaps, you can do it in O(n): copy the intervals that end before the new one starts, absorb every interval that starts at or before its end by taking the smaller start and larger end, then copy the rest. Inserting [4, 10] into [[1, 3], [6, 8], [12, 15]] gives [[1, 3], [4, 10], [12, 15]] either way.
What if touching intervals should stay separate?
Change start <= merged[-1][1] to start < merged[-1][1] in the sweep (and <= to < in both brute-force checks). Then [[2, 5], [5, 8], [10, 11]] comes back unchanged as [[2, 5], [5, 8], [10, 11]] instead of [[2, 8], [10, 11]].
Does it work if the intervals are tuples instead of lists?
Yes. sorted orders tuples the same way, and the sweep unpacks start, end and appends a new list, so it never tries to assign into a tuple. merge([(4, 7), (1, 3), (6, 9), (12, 15)]) returns [[1, 3], [4, 9], [12, 15]]. If you need tuples back, return [tuple(iv) for iv in merged].
How do I count how many intervals were merged away, or the total length covered?
Compare the lengths: len(intervals) - len(merged) is how many intervals disappeared into others. For the covered length, sum the merged intervals, which never double-count: sum(end - start for start, end in merged). For [[4, 7], [1, 3], [6, 9], [12, 15]] that gives 1 and 10.
Why sort by start and not by end?
Sorting by start guarantees that once an interval starts after the current merged end, nothing later can reach back and overlap anything before it. Sorting by end does not: [[5, 6], [1, 10]] is already sorted by end, but [1, 10] reaches past [5, 6] on the left. The same sweep run in end order extends [5, 6] to [5, 10] and returns [[5, 10]], losing the start at 1.
FAQ for JavaScript
Why do I get the wrong answer if I call sort() with no comparator?
Without a comparator, JavaScript turns each element into a string and compares those, so the pair [10, 11] becomes "10,11" and lands before "2,5". [[10, 11], [2, 5], [5, 8]].toSorted() prints [ [ 10, 11 ], [ 2, 5 ], [ 5, 8 ] ], and sweeping that order returns [ [ 10, 11 ] ], swallowing both smaller ranges. With (a, b) => a[0] - b[0] the same input gives [ [ 2, 8 ], [ 10, 11 ] ].
Does merge change the array I pass in?
Not the version above, but it is easy to slip. toSorted (Node 20 and later; use [...intervals].sort(...) on older runtimes) copies only the outer array, so the inner pairs are still the caller's objects. If the loop pushes the original pair and later writes last[1], merging [[1, 3], [2, 6], [8, 9]] returns [ [ 1, 6 ], [ 8, 9 ] ] but leaves the input as [ [ 1, 6 ], [ 2, 6 ], [ 8, 9 ] ]. Pushing [start, end] keeps it at [ [ 1, 3 ], [ 2, 6 ], [ 8, 9 ] ].
How do I keep ranges that only touch as separate entries?
Make the comparison strict: start < last[1] in the sweep, and < instead of <= in both brute-force tests. With that change [[2, 5], [5, 8], [10, 11]] comes back as [ [ 2, 5 ], [ 5, 8 ], [ 10, 11 ] ].
My ranges are objects with start and end properties. What changes?
Only the field access. Sort with (a, b) => a.start - b.start, destructure { start, end } in the loop, compare against last.end, and push { start, end }. For [{ start: 4, end: 7 }, { start: 1, end: 3 }, { start: 6, end: 9 }] Node prints [ { start: 1, end: 3 }, { start: 4, end: 9 } ]. With Date values, subtraction in the comparator works, but Math.max(new Date(0), new Date(1000)) returns the number 1000, not a Date, so pick the later end with > if you need a Date back.
How do I get the total length the ranges cover?
Merge first so no stretch is counted twice, then add up the widths: merged.reduce((sum, [s, e]) => sum + (e - s), 0). For [[4, 7], [1, 3], [6, 9], [12, 15]] that is 10, and intervals.length - merged.length shows that 1 range was absorbed into another.
FAQ for TypeScript
Why does sort() without a comparator give the wrong order?
With no comparator, sort converts each element to a string, so [10, 11] becomes "10,11" and sorts before "2,5". TypeScript does not catch this, because calling sort() on a number[][] is perfectly well typed. Always pass a comparator that looks at index 0.
Is (a, b) => a[0] - b[0] safe here?
In TypeScript, yes: a number is a 64-bit float, so the difference of two values within ±2×10⁹ is exact. The comparison form a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0 is used above because it stays correct for any values, including ones far beyond 2⁵³, and it is the habit that keeps the same code safe when ported to C, C++ or Java, where subtracting two 32-bit ints can overflow.
Should an interval be typed as a tuple?
[number, number] says exactly what a row is, and then const [start, end] = iv is checked, and returning a three-element row is a compile error. The harness signature uses number[][], which accepts tuples too, so you can declare merged: [number, number][] inside the function and return it unchanged.
Does sorting change the array the caller passed in?
Array.prototype.sort sorts in place, so intervals.sort(...) would reorder the caller's array. [...intervals] copies the outer array first. The copy still holds the caller's inner arrays, which is why the sweep pushes [start, end] and writes only into its own pairs.
How do I keep intervals that only touch as separate ranges?
Make every comparison strict: start < last[1] in the sweep and < in both halves of the brute-force overlap test. [[2, 5], [5, 8], [10, 11]] then stays as three ranges instead of becoming [[2, 8], [10, 11]].
FAQ for Java
Does merge modify the int[][] I pass in?
No, but only thanks to two deliberate choices. intervals.clone() is shallow: the new outer array points at the very same int[] rows. Sorting the clone protects the caller's row order, and adding new int[] {iv[0], iv[1]} keeps the end-stretching off the caller's rows. Change that line to merged.add(iv) and, after merging {{4, 7}, {1, 3}, {6, 9}, {12, 15}}, the input reads [[4, 9], [1, 3], [6, 9], [12, 15]] instead of staying [[4, 7], [1, 3], [6, 9], [12, 15]]. Pass intervals itself to Arrays.sort and the caller's order changes as well.
Why use Comparator.comparingInt rather than (a, b) -> a[0] - b[0]?
Java int arithmetic wraps without any error. Take {{2000000000, 2000000001}, {-2000000000, -1999999999}}: the difference of the two starts exceeds Integer.MAX_VALUE, wraps to a negative number, and the sort places the row starting at 2000000000 first. The sweep then returns [[2000000000, 2000000001]] and one interval is gone. comparingInt compares through Integer.compare, never subtracts, and yields [[-2000000000, -1999999999], [2000000000, 2000000001]]. One of the hidden cases is exactly this input.
Would a record be better than an int[] for one interval?
Often, yes. record Interval(int start, int end) {} names both fields, gets equals, hashCode and a readable toString for free, and cannot be mutated, so the aliasing trap above disappears. The sweep would then replace the last element instead of writing into it: merged.set(merged.size() - 1, new Interval(last.start(), Math.max(last.end(), iv.end()))), with the sort key written as Comparator.comparingInt(Interval::start). The bare int[][] shape stays common simply because many problem statements and test harnesses hand you one.
How do I treat intervals that only touch as separate?
Turn each <= into <. In the sweep that means iv[0] < merged.getLast()[1]; in the brute force it applies to both halves of the intersection test. {{2, 5}, {5, 8}, {10, 11}} then stays as three rows, [[2, 5], [5, 8], [10, 11]], rather than collapsing to [[2, 8], [10, 11]] as it does now.
Why must the sort key be the start rather than the end?
The sweep relies on one promise: after a gap, every remaining row begins to the right of it. Ordering by start keeps that promise and ordering by end breaks it. {{5, 6}, {1, 10}} is already in end order, yet {1, 10} begins left of {5, 6}. Run the loop with Comparator.comparingInt(a -> a[1]) and it grows {5, 6} into {5, 10}, returns [[5, 10]], and the start at 1 is lost.
FAQ for Go
Should one interval be a [2]int or a []int in Go?
Prefer [2]int when the type is yours to pick. A []int value is a small header that points at a backing array, so appending the caller's inner slice to merged shares that array, and the later merged[n-1][1] = … writes straight into the input. On [][]int{{1, 3}, {2, 6}} that sweep returns [[1 6]] but silently turns the input into [[1 6] [2 6]]. When an API hands you [][]int, as the workbench does, append []int{iv[0], iv[1]} so each output pair owns its memory. Arrays are values, so a [2]int version is immune, and fmt prints both types identically.
Does slices.SortFunc sort the caller's slice in place, and how does it differ from sort.Slice?
Both reorder in place, which is the whole reason for slices.Clone ahead of the sort. Without the clone, merge still returns [[1 3] [4 9] [12 15]] for the first example, yet the caller's slice is left shuffled as [[1 3] [4 7] [6 9] [12 15]]. slices.SortFunc is generic and wants a three-way comparison (negative, zero, positive), which cmp.Compare returns directly. sort.Slice takes an any plus a less-than function over indexes and swaps through reflection, so the element type goes unchecked at compile time; new code reads better with the slices version.
Is the result nil or an empty slice when there is nothing to merge?
In the sweep it is nil: var merged [][]int is only ever appended to, so with no input it is returned untouched. That is harmless for len, range and fmt.Println, which shows [], and the workbench runner reports it as an empty array. It matters with encoding/json, which writes a nil slice as null and an empty one as []. If your API must emit [], start from merged := make([][]int, 0, len(intervals)), which also sizes the backing array once so append never has to regrow it.
How do I keep intervals that only touch from merging?
Make every comparison strict. In the sweep the condition becomes iv[0] < merged[n-1][1], and in the brute force both halves of the overlap test switch from <= to <. After that change the second example keeps all three pairs and prints [[2 5] [5 8] [10 11]] where the shipped code prints [[2 8] [10 11]].
How can I add one interval to a slice that is already merged?
Calling merge(append(slices.Clone(merged), iv)) works and costs O(n log n). Because the slice is sorted with no overlaps, a linear walk is enough: append each pair whose right end is below iv[0] to a new slice, fold every following pair whose left end is at most iv[1] into iv using min and max, append iv, then finish with out = append(out, merged[i:]...). Adding []int{4, 10} to [][]int{{1, 3}, {6, 8}, {12, 15}} gives [[1 3] [4 10] [12 15]] with either method.
FAQ for C#
Does Merge modify the int[][] I pass in?
No, but only because of two choices. OrderBy returns a new sequence and leaves intervals in its original order, unlike Array.Sort(intervals, …), which sorts the outer array in place. And the sweep adds new[] { iv[0], iv[1] } instead of iv itself, so the Math.Max write lands on a copy. Change that line to merged.Add(iv) and after merging { {4, 7}, {1, 3}, {6, 9}, {12, 15} } the caller's first row reads [4, 9] instead of [4, 7].
Why OrderBy and not Array.Sort with (a, b) => a[0] - b[0]?
Subtracting two int values near the limits wraps silently in an unchecked context. For { {2000000000, 2000000001}, {-2000000000, -1999999999} } the difference of the starts exceeds int.MaxValue, turns negative, and the comparison sorts the row starting at 2000000000 first; the sweep then returns [[2000000000, 2000000001]] and one interval is gone. OrderBy(iv => iv[0]) compares through Comparer<int>.Default, which never subtracts. If you prefer Array.Sort on a copy, pass (a, b) => a[0].CompareTo(b[0]). One of the hidden cases is exactly this input.
Is OrderBy a stable sort, and does it matter here?
Yes, LINQ OrderBy is stable: rows with the same start keep their input order. Array.Sort is not stable. For this problem it makes no difference, because two rows with the same start always overlap and merge into one, so the order in which they are visited cannot change the result.
Would a record struct be better than int[] for one interval?
Usually. readonly record struct Interval(int Start, int End); names the fields, gets value equality and a readable ToString, and cannot be mutated, so the aliasing trap above disappears. The sweep then replaces the last element instead of writing into it: merged[^1] = last with { End = Math.Max(last.End, iv.End) }, with the sort key written as OrderBy(iv => iv.Start). The bare int[][] shape stays common simply because many statements and test harnesses hand you one.
How do I treat intervals that only touch as separate?
Turn each <= into <. In the sweep that is iv[0] < merged[merged.Count - 1][1]; in the brute force it applies to both halves of the overlap test. { {2, 5}, {5, 8}, {10, 11} } then stays three rows, [[2, 5], [5, 8], [10, 11]], instead of collapsing to [[2, 8], [10, 11]] as it does now.
FAQ for C++
Can I sort with a comparator that returns a[0] - b[0]?
No, for two reasons. std::sort wants a strict weak ordering that returns bool, so any nonzero difference converts to true and the order is broken. And with starts of 2000000000 and -2000000000 the difference overflows int, which is undefined behaviour. Compare with a[0] < b[0]; one of the hidden cases uses exactly those values.
Why not just call sort(intervals.begin(), intervals.end())?
It works, and the default operator< on vector<int> is lexicographic, so it orders by start and then by end. But intervals arrives by reference, so sorting it in place reorders the caller's data. Copying first costs O(n) next to the O(n log n) sort; if the caller does not care, sorting in place saves that copy.
Is a vector<vector<int>> the best type for intervals?
Each inner vector<int> is its own heap allocation. vector<pair<int, int>> or vector<array<int, 2>> keeps the pairs contiguous, sorts faster and gets lexicographic < for free. The nested vector is the shape this problem hands you, so the solutions keep it.
Why is erase in a loop slow?
erase(begin() + j) shifts every later row one place left, which is O(n) per call. Together with restarting the pair scan after each merge, that is what makes the brute force O(n³). The sweep never erases: it only appends or updates back().
Does merged.push_back(iv) alias the caller's rows?
No. Unlike Java or JavaScript, a C++ vector<int> is a value: push_back(iv) copies the row, so writing merged.back()[1] never touches sorted or intervals. Use push_back(move(...)) only when the source is yours to give up.
FAQ for C
What do returnSize and returnColumnSizes mean?
A returned int** carries no lengths, so the function reports them through out-parameters. *returnSize is the number of rows, and *returnColumnSizes points to a malloc'ed array with one length per row, here always 2. The caller frees each row, the row array and the column-size array.
Why does the qsort comparator not return a - b?
Starts reach ±2×10⁹, so 2000000000 - (-2000000000) is 4×10⁹, past INT_MAX. Signed overflow is undefined behaviour in C, and in practice the result wraps negative and the sort puts the larger start first. (a > b) - (a < b) gives -1, 0 or 1 with no arithmetic on the values; a hidden case checks exactly this.
Why qsort an array of row pointers instead of intervals itself?
qsort(intervals, ...) would reorder the caller's array. Copying the pointers with memcpy costs O(n) and leaves both the caller's array and the rows it points to unchanged. Each element passed to the comparator is then an int*, so the comparator receives a pointer to it and casts with *(int* const*)x.
Why malloc every output row separately?
The int** shape means each row is its own pointer the caller can free. A single block of 2 * count ints with row pointers into it would also work in your own code, but a caller that frees row by row would then free memory it never got from malloc.
What happens with an empty input?
An empty input arrives with intervalsSize of 0. The function sets *returnSize = 0 and *returnColumnSizes = NULL and returns NULL, so there is nothing to free. Checking first also avoids calling malloc(0), whose result may or may not be NULL.
FAQ for Kotlin
What is the difference between sortBy and sortedBy here?
sortBy sorts a MutableList (or an Array) in place and returns Unit; sortedBy leaves the receiver alone and returns a new List. The sweep uses intervals.sortedBy { it[0] } so the caller's array keeps its order. Both are stable and compare the keys with compareTo, never by subtraction.
Why copyOf() before adding a row to the result?
sortedBy copies the outer list, but the IntArray rows inside are the caller's objects. Writing last[1] = ... into one of them would change the input. With merged.add(iv) instead of merged.add(iv.copyOf()), merging [[4, 7], [1, 3], [6, 9], [12, 15]] leaves the caller holding [4, 9] where [4, 7] was.
Can I sort with sortedWith { a, b -> a[0] - b[0] }?
Not safely. Starts reach ±2 × 10⁹, and Int subtraction wraps silently past Int.MAX_VALUE. For [[2000000000, 2000000001], [-2000000000, -1999999999]] the difference is negative, the positive interval sorts first and the sweep loses one. Use sortedBy { it[0] } or compareBy<IntArray> { it[0] }, which compare without subtracting.
What does break@search do?
A plain break only leaves the innermost for. Labeling the outer loop search@ lets break@search leave both at once, which the brute force needs because removeAt(j) has just changed the list it was iterating over.
Would a List<IntRange> be nicer than Array<IntArray>?
For your own code, often yes: IntRange has first and last, and a.first <= b.last && b.first <= a.last reads well. The sweep would replace the last element with merged[merged.size - 1] = last.first..maxOf(last.last, r.last). The signature here uses Array<IntArray> because the cases arrive as rows of two numbers.
FAQ for Rust
Why can the function sort intervals without copying it?
The parameter is Vec<Vec<i32>> by value, so the caller has moved ownership in and nobody else can see the vector. Writing mut intervals in the signature lets you call sort_unstable_by_key on it directly. for iv in intervals then consumes it, so each row is moved into merged instead of cloned.
Why sort_unstable_by_key rather than sort_by_key?
Both order the rows by the key iv[0]. The unstable variant does not keep equal starts in their original order, which the sweep does not care about, and it sorts in place without the extra buffer the stable merge sort allocates. A plain intervals.sort() would also work, since Vec<i32> compares lexicographically.
Does the borrow checker accept push inside the match on last_mut()?
Yes. The &mut that last_mut() returns is only used in the first arm. In the _ arm it is no longer live, so non-lexical lifetimes allow the second mutable borrow for merged.push(iv). What decides is where the reference is still used, not the block it was created in.
Can comparing or subtracting starts overflow i32?
Comparisons never overflow, and the values stay within ±2 × 10⁹, which fits i32. A comparator such as sort_by(|a, b| (a[0] - b[0]).cmp(&0)) would subtract two starts, and 2000000000 - (-2000000000) panics with "attempt to subtract with overflow" in a debug build. Sorting by key compares with Ord, so the problem never comes up.
Would [i32; 2] or a tuple be a better element type?
For your own code, yes: Vec<[i32; 2]> or Vec<(i32, i32)> stores both numbers inline, with no heap allocation per interval, and let [start, end] = iv; destructures it. The signature uses Vec<Vec<i32>> because that is how the cases arrive, rows of numbers.
FAQ for Swift
Why does writing to last not change merged?
merged.last returns an [Int]? copy of the final element, because arrays are value types. Changing that copy leaves merged as it was. Write through the subscript instead: merged[merged.count - 1][1] = ... edits the element stored in the array.
Do I need to copy intervals before sorting it?
No. A parameter is a constant, and sorted(by:) returns a new array, so the caller's value cannot change. Even var result = intervals followed by result.sort(by:) only sorts the local copy; copy-on-write duplicates the storage the moment you mutate it.
What is the difference between sort(by:) and sorted(by:)?
sort(by:) reorders a var array in place and returns nothing; sorted(by:) works on any sequence and returns a new array. The closure is an "are in increasing order" predicate, so { $0[0] < $1[0] } orders by start. It must be a strict <, not <=.
Can the values overflow Int?
No. Int is 64-bit on every platform Swift runs here, and the values stay within ±2 × 10⁹. The solutions only compare and take min and max, so there is no arithmetic that could trap anyway.
Would ClosedRange<Int> be a better type than [Int]?
For your own code, often yes: a.overlaps(b) is built in for ClosedRange, and touching ranges such as 2...5 and 5...8 count as overlapping, which matches this problem. The sweep would replace the last element with last.lowerBound...max(last.upperBound, r.upperBound). The signature uses [[Int]] because the cases arrive as rows of two numbers.
FAQ for PHP
Does usort change the array the caller passed in?
No. usort takes its argument by reference, but $intervals is the function's own copy: PHP passes arrays by value with copy-on-write, so the caller's array is duplicated the moment usort writes to it. Only a parameter declared array &$intervals would let the sort reach the caller.
Why <=> instead of returning $x[0] - $y[0]?
The spaceship operator returns -1, 0 or 1 and states the intent. Subtraction happens to work for these values on 64-bit PHP, where integers hold far more than ±2 × 10⁹, but it breaks for floats (the callback's return is cast to int, so 0.5 becomes 0) and it reads as a trick. $x[0] <=> $y[0] is the idiom.
Why array_splice and not unset to drop a row?
unset($result[$j]) leaves a hole in the keys, so $result[$j] no longer exists, the for loop reads a missing index, and json_encode turns an array with gaps into an object. array_splice($result, $j, 1) removes the row and renumbers the keys from 0. usort renumbers too, so the returned array is always a list.
Can I write through end($merged) to stretch the last interval?
No. end() returns a copy of the last value, so end($merged)[1] = ... is not even valid syntax and assigning to a copy would change nothing. Index the last row directly, $merged[count($merged) - 1][1], or keep a reference with $last = &$merged[array_key_last($merged)].
How do I keep intervals that only touch separate?
Change <= to < in the overlap test: $start < $merged[$last][1] in the sweep, and both halves of the brute-force check. [[2, 5], [5, 8], [10, 11]] then comes back as three intervals instead of [[2, 8], [10, 11]].
FAQ for Ruby
Why is the second value called finish and not end?
end is a reserved word in Ruby, so |(start, end), merged| is a syntax error. Any other name works; finish, stop or hi are common choices.
Does merged.last[1] = ... really change merged?
Yes. merged.last returns the inner array object itself, not a copy, so assigning to its index edits the row stored in merged. That is also why the sweep appends a new [start, finish] rather than the caller's row: stretching the end of a shared row would change the input.
What is the difference between sort_by and sort_by!?
sort_by returns a new array and leaves intervals alone; sort_by! sorts the receiver in place, which would reorder the array the caller passed in. intervals.sort also works, since arrays compare element by element, but sort_by(&:first) says what the key is and computes it once per row.
Does combination(2) build every pair up front?
Called without a block, combination(2) returns an Enumerator, so find pulls pairs one at a time and stops at the first overlap. The index array (0...result.size).to_a is rebuilt on every pass, which is fine for 200 rows but part of why the brute force is the slow approach.
Can the values overflow?
No. Ruby Integer grows to arbitrary size, and the code only compares values and picks min and max, so ±2 × 10⁹ is no different from small numbers.
FAQ for Dart
Why [...intervals]..sort(...) and not intervals.sort(...)?
List.sort sorts in place and returns void, so intervals.sort(...) would reorder the caller's list and give you nothing to chain on. The spread [...intervals] makes a new outer list, and the cascade ..sort(...) sorts it and evaluates to the list itself, ready to assign.
Does the spread copy the inner lists too?
No, [...intervals] is a shallow copy: the rows inside are the caller's List<int> objects. That is why the sweep adds [iv[0], iv[1]] instead of iv. With merged.add(iv), writing merged.last[1] = ... would stretch the caller's row.
Is a[0] - b[0] safe as the comparator?
On the Dart VM int is 64-bit, so the difference of two values within ±2 × 10⁹ fits and the sign is right. a[0].compareTo(b[0]) is still the idiom: it says what it does and never depends on the range of the values.
Where do min and max come from?
They are top-level functions in dart:math, hence import 'dart:math'; at the top. They are generic over num, so max(merged.last[1], iv[1]) stays an int and needs no cast.
How do I keep intervals that only touch separate?
Change <= to < in the overlap test: iv[0] < merged.last[1] in the sweep and both halves of the brute-force check. [[2, 5], [5, 8], [10, 11]] then comes back as three intervals instead of [[2, 8], [10, 11]].
FAQ for Scala
Does sortBy change the array I pass in?
Array#sortBy returns a new array and leaves the original order alone. The copy is shallow, though: the rows inside are still the caller's Array[Int] objects, which is why the sweep appends Array(iv(0), iv(1)) instead of iv. Writing last(1) = ... into a shared row would stretch the caller's interval.
Why not sortWith((a, b) => a(0) - b(0) < 0)?
Subtracting two Int starts can overflow: 2000000000 - (-2000000000) wraps to a negative number, so the comparison flips and the sweep drops an interval. sortBy(_(0)) and sortWith(_(0) < _(0)) compare with Ordering[Int] or < and never subtract.
Why use boundary and break instead of return in the helper?
A for over ranges is sugar for foreach with a closure, and a return inside it is a non-local return, which Scala 3 warns about on every compile. boundary { ... break(value) ... } from scala.util.boundary exits the block with value directly, so the helper reads the same and compiles cleanly.
Why ArrayBuffer instead of a List?
Both passes add at the end and read or change the last element. ArrayBuffer does that in constant time and supports remove(j) and indexed updates for the brute force. An immutable List prepends cheaply, so a functional version would foldLeft with the newest interval at the head and reverse at the end.
What does _(0) mean in sortBy(_(0))?
It is shorthand for iv => iv(0): the placeholder _ stands for the parameter, and (0) calls apply(0) on the row, which reads its first element. Arrays are indexed with parentheses in Scala, not square brackets.