Merge Intervals

Medium Arrays

Merge all overlapping intervals. Sort by start, then fold overlapping intervals into the last one.

Sample input

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

Sample output

1 6 8 10 15 18

Solution

def merge(intervals):
    intervals.sort()
    result = []
    for start, end in intervals:
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

for start, end in merge([[1, 3], [2, 6], [8, 10], [15, 18]]):
    print(start, end)

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const result = [];
  for (const [start, end] of intervals) {
    const last = result[result.length - 1];
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      result.push([start, end]);
    }
  }
  return result;
}

for (const [s, e] of merge([[1, 3], [2, 6], [8, 10], [15, 18]])) {
  console.log(s + " " + e);
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static List<int[]> merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();
        for (int[] interval : intervals) {
            if (!result.isEmpty() && interval[0] <= result.get(result.size() - 1)[1]) {
                result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], interval[1]);
            } else {
                result.add(interval);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        for (int[] interval : merge(intervals)) {
            System.out.println(interval[0] + " " + interval[1]);
        }
    }
}

fun merge(intervals: Array<IntArray>): List<IntArray> {
    intervals.sortBy { it[0] }
    val result = mutableListOf<IntArray>()
    for (interval in intervals) {
        if (result.isNotEmpty() && interval[0] <= result.last()[1]) {
            result.last()[1] = maxOf(result.last()[1], interval[1])
        } else {
            result.add(interval)
        }
    }
    return result
}

fun main() {
    val intervals = arrayOf(intArrayOf(1, 3), intArrayOf(2, 6), intArrayOf(8, 10), intArrayOf(15, 18))
    for (interval in merge(intervals)) {
        println("${interval[0]} ${interval[1]}")
    }
}

func merge(_ intervals: [[Int]]) -> [[Int]] {
    let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
    var result = [[Int]]()
    for interval in sortedIntervals {
        if var last = result.last, interval[0] <= last[1] {
            last[1] = max(last[1], interval[1])
            result[result.count - 1] = last
        } else {
            result.append(interval)
        }
    }
    return result
}

for interval in merge([[1, 3], [2, 6], [8, 10], [15, 18]]) {
    print("\(interval[0]) \(interval[1])")
}

List<List<int>> merge(List<List<int>> intervals) {
  intervals.sort((a, b) => a[0].compareTo(b[0]));
  final result = <List<int>>[];
  for (final interval in intervals) {
    if (result.isNotEmpty && interval[0] <= result.last[1]) {
      result.last[1] = result.last[1] > interval[1] ? result.last[1] : interval[1];
    } else {
      result.add([interval[0], interval[1]]);
    }
  }
  return result;
}

void main() {
  for (final interval in merge([[1, 3], [2, 6], [8, 10], [15, 18]])) {
    print('${interval[0]} ${interval[1]}');
  }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result;
    for (auto& interval : intervals) {
        if (!result.empty() && interval[0] <= result.back()[1]) {
            result.back()[1] = max(result.back()[1], interval[1]);
        } else {
            result.push_back(interval);
        }
    }
    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    for (auto& interval : merge(intervals)) {
        cout << interval[0] << " " << interval[1] << endl;
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    const int *ia = (const int *) a;
    const int *ib = (const int *) b;
    return ia[0] - ib[0];
}

int main() {
    int intervals[][2] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    int n = 4;
    qsort(intervals, n, sizeof(intervals[0]), cmp);
    int result[10][2];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (count > 0 && intervals[i][0] <= result[count - 1][1]) {
            if (intervals[i][1] > result[count - 1][1]) result[count - 1][1] = intervals[i][1];
        } else {
            result[count][0] = intervals[i][0];
            result[count][1] = intervals[i][1];
            count++;
        }
    }
    for (int i = 0; i < count; i++) {
        printf("%d %d\n", result[i][0], result[i][1]);
    }
    return 0;
}