56.merge-intervals.md

56. Merge Intervals

Interval

The idea is that we sort the array first by the start, so that we can iterate every interval and merge one by one:

• We assign the first interval to merged.
• For each interval, we check if it's overlapped with merged, if so, we merge them.
• If not, we add the merged to the result and assign the current interval to merged.

// Sort by start
[[1, 3], [2, 6], [8, 10], [15, 18]]
 merged  toMerge
         [1, 6], [8, 10], [15, 18]]
                 toMerge
                 [1, 10], [15, 18]]
                          toMerge

// After merging
[1, 10], [15, 18]

To merge the two intervals, we just need to keep the smaller start and the larger end, that is min(merged[0], toMerge[0]), max(merged[1], toMerge[1])

// 1. Fully Overlapped: just keep the longer interval [1, 4]
 1  2  3  4  5  6  7  8
 |--------|
    |--|

// Merged:
 1--------4

// 2. Partially Overlapped: merged, [1, 5]
 1  2  3  4  5  6  7  8
 |--------|
       |-----|

// Merged:
 1-----------5

// 3. Adjacent: extended, [1, 5]
 1  2  3  4  5  6  7  8
 |--------|
          |--|

// Merged:
 1-----------5

// 4. No Overlap: keep both, [1, 4][6, 8]
[1      4]   [6   8]

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    Arrays.sort(intervals) { i1, i2 -> i1[0] - i2[0] }

    val results = mutableListOf<IntArray>()
    var merged = intervals[0]
    // Remember to add the merged interval to results first (or later)
    results.add(merged)
    for (i in 1 until intervals.size) {
        val toMerge = intervals[i]
        if (isOverlapped(merged, toMerge)) {
            merged[0] = minOf(merged[0], toMerge[0])
            merged[1] = maxOf(merged[1], toMerge[1])
        } else {
            // not overlap, the order is important
            merged = toMerge
            results.add(merged) // We add the "new" merged interval to results
        }
    }
    return results.toTypedArray()
}

// Or we can add `merged` later:
fun merge(intervals: Array<IntArray>): Array<IntArray> {
    Arrays.sort(intervals) { i1, i2 -> i1[0] - i2[0] }
    var merged = intervals[0]
    val results = mutableListOf<IntArray>()
    for (i in 1 until intervals.size) {
        val toMerge = intervals[i]

        if (isOverlapped(merged, toMerge)) {
            merged[0] = minOf(merged[0], toMerge[0])
            merged[1] = maxOf(merged[1], toMerge[1])
        } else {
            // The order is important
            results.add(merged) // We add the "old" merged interval to results
            merged = toMerge
        }
    }
    // Add the last merged interval
    results.add(merged)
    return results.toTypedArray()
}

• Time Complexity: O(n lg n) for sorting, O(n) to merge, total time is O(n lg n).
• Space Complexity: O(lg n) for sorting.

Line Sweep

合并区间，一般做法是先排序再合并。如果遇到follow-up,比如intervals是stream形式给出的，排序的解法就处理不了。但是treeMap可以，interval以数据流形式出现，每一步interval insert之后，整体数组保持有序。

TODO: This is WA. Try this solution

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val map = TreeMap<Int, Int>()
    for ((start, end) in intervals) {
        map[start] = (map[start] ?: 0) + 1
        map[end] = (map[end] ?: 0) - 1
    }
    var start = 0
    val results = mutableListOf<IntArray>()
    var previous = 0
    var value = 0
    for ((k, v) in map) {
        value += v
        if (value > 0 && previous == 0) {
            start = k
        } else if (value == 0 && previous > 0) {
            results.add(intArrayOf(start, k))
        }
        previous = value
    }
    return results.toTypedArray()
}