435.non-overlapping-intervals.md

435. Non-overlapping Intervals

Greedy

Sorted By end

Sort the intervals by the end time, this lets us pick the interval that finishes earilest, we leave as much space as possible for the rest intervals (more space for other intervals). We reduce the chance of overlaps later on, thus maximizing the number of intervals we can keep.

For the next interval:

• If they have the same start, we should always remove the interval with the larger end time, the larger end time means it's more likely to overlap with other intervals.

-----|
       * // `start` is the same
       |--|
            |---|  |---|     // These intervals can be added if we remove the below one, so that it leads to minimum removal
       |-----------------|   // We should remove this one, #removal = 1

// What if we don't remove the interval with the larger `end` time?
-----|
       * // `start` is the same
       |-----------------|   // We don't remove this one, so that we can't add the below intervals
       |--|
            |---|  |---|     // These intervals can NOT be added, #removal = 3, not optimal!

• If they have the same end, it doesn't matter which one to remove, it won't affect the rest of the intervals because we check if overlapping by start.

// If we have [3, 5] first, and check [1, 5], [6, 8] later.
1, 2, 3, 4, 5, 6, 7, 8, 9
      |-----|
|-----------|
               |-----|

// Or iterating [1, 5] first, and check [3, 5], [6, 8] later, the result is the same.
1, 2, 3, 4, 5, 6, 7, 8, 9
|-----------|
      |-----|
               |-----|

• Why sort by end? This is because, the interval with the earliest end time produces the maximal capacity to hold rest intervals.
• Practical example --> In the case of scheduling meeting and trying to remove conflicting meetings, If we want to have maximum meetings in a day, we should opt for meetings which are ending sooner.
• 這題的題意可以表達為「你今天有好幾個會議，你最多能參與幾個會議而不會有衝突？」那麼這樣我們自然會想到，優先參加「結束時間早」的會議，這樣才能讓我們有更多的時間參加其他的會議。

fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] } // Sort by `end`
    var removal = 0
    var previous = intervals.first()
    for (i in 1 until intervals.size) {
        val (start, end) = intervals[i]
        if (start < previous[1]) removal++
        else previous = intervals[i]
    }
    return removal
}

// Or equivalently, we count non-overlapping intervals
fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] } // Sort by end
    var nonOverlap = 1 // The first interval is always non-overlapping
    var previousEnd = intervals.first()[1]
    for (i in 1 until intervals.size) {
        val (start, end) = intervals[i]
        if (previousEnd <= start) {
            nonOverlap++
            previousEnd = end
        }
    }
    return intervals.size - nonOverlap
}

Sorted By start

It's OK to sorted by the start time, but we should always remove the interval with the larger end time, so that we can add more intervals later on. Either sort by start time or end time will work. The essence is that when you iterate through the sorted intervals (either by start or end time), when you see overlapping intervals, always keep the one whose end is shorter (earlier), so it's less likely to overlap with rest of intervals (greedy thinking).

If we sort by start time, we don't guarantee that the earliest start time have the earliest end time, so we need to track the previous end time to make sure we remove the interval with the larger end time.

// If we sort by `start` time, and we don't track the smaller previous end time, which leads to WA (2).
|___________|               interval A 
  |___|                     interval B (removed)         
        |___|               interval C (removed)
                |______|    interval D

// But if we sort by `start` time, and we track the smaller previous end time, it's AC (1 to remove).
|___________|               interval A (removed)
  |___|                     interval B         
        |___|               interval C 
                |______|    interval D

fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[0] } // Sort by `start`
    var removal = 0
    var previousEnd = intervals.first()[1]
    for (i in 1 until intervals.size) {
        val (start, end) = intervals[i]
        if (start < previousEnd) {
            removal++
            // We still keep the interval with the smaller `end` time
            previousEnd = minOf(previousEnd, end)
        }
        else previousEnd = intervals[i][1]
    }
    return removal
}

Time complexity: O(n lg n) for sorting, O(n) for iterating the intervals, so the total time complexity is O(n lg n). Space complexity: O(1).

Dry Run

1, 2, 3, 4, 5, 6, 7, 8, 9
   |--------|
|-----------|
|-----|
   |-----|
         |--|
                  |------|

// The final result, expected removal = 3
1, 2, 3, 4, 5, 6, 7, 8, 9
|-----|  |--|     |-----|

// Sorted by `end`
[1, 3]
[2, 4]
[2, 5]
[1, 5]
[4, 5]
[7, 9]

// Sorted by `end`, 1st approach
Checking interval: [2, 4]	Overlapping interval: [2, 4], removal: 1
Checking interval: [2, 5]	Overlapping interval: [2, 5], removal: 2
Checking interval: [1, 5]	Overlapping interval: [1, 5], removal: 3
Checking interval: [4, 5]	Non-overlapping interval: [4, 5], previous: [4, 5]
Checking interval: [7, 9]	Non-overlapping interval: [7, 9], previous: [7, 9]

// Sorted by `end`, 2nd approach
Previous end: 3
Checking interval: [2, 4]	Overlapping interval: [2, 4], previousEnd: 3
Checking interval: [2, 5]	Overlapping interval: [2, 5], previousEnd: 3
Checking interval: [1, 5]	Overlapping interval: [1, 5], previousEnd: 3
Checking interval: [4, 5]	Nnon-overlapping interval: [4, 5], previousEnd: 5
Checking interval: [7, 9]	Nnon-overlapping interval: [7, 9], previousEnd: 9
Total non-overlapping intervals: 3

// Sorted by `start`, 3rd approach
First interval: [1, 3], previousEnd: 3
Checking interval: [1, 5]	Overlapping interval: [1, 5], previousEnd: 3
Checking interval: [2, 4]	Overlapping interval: [2, 4], previousEnd: 3
Checking interval: [2, 5]	Overlapping interval: [2, 5], previousEnd: 3
Checking interval: [4, 5]	Non-overlapping interval: [4, 5], previousEnd: 5
Checking interval: [7, 9]	Non-overlapping interval: [7, 9], previousEnd: 9