435. Non-overlapping Intervals

Greedy

Idea!! We need to remove the minimum number of intervals -> equivalent to keep the most non-overlapping intervals. Sorting intervalsl helps in greedy selection.

Sorted By `end`

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

For example, we have two intervals now, then we must remove B to create more space for the later intervals C (only 1 removal, greedy thinking):

// Current intervals
A: |----|   
B: |---------------| X 

// If we have another interval later:
C:        |---|
D:              |----|

If we remove A and keep B, then B and C, D are overlapping, so we also have to remove B or C, D which leads to 3 removals.

After sorting by end, let's check the next interval:

If the upcoming interval is overlapping with the previous one, we should remove the interval with the larger end time: It doesn't matter which one to remove, because they create the same space for the rest of the intervals.

// Previous interval
    |----|

// Current interval: same `end` time, but different `start` time
|--------|
    |----| 
       |-|

If the upcoming interval is larger end time, it may or may not overlap with the previous one, so we should:
- Overlapping: Remove the interval with the larger end time.
- Non-overlapping: Keep both, and update the previous end time.

// Previous interval
    |----|

// Current interval: larger `end` time, may or may not overlap with the previous one
       |-----|  [X]
            |-----| [O]

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 previousEnd = intervals.first()[1]
    for (i in 1 until intervals.size) {
        val (start, end) = intervals[i]
        if (start < previousEnd) {
            removal++
        } else {
            previousEnd = end
        }
    }
    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

用「開始」時間排序可不可以？也是可以，只不過開始時間排序代表我們求得是「重疊」的區間，remove 記錄的就是重疊的區間數量。

如果我們用「開始」時間排序，我們一定能找到最先開始的會議，但是最先開始的，不一定最先結束。

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, as same as above
            // We need to keep the earliest end time, so that we can have more spaces for future intervals
            // If we don't do this, check below example
            previousEnd = minOf(previousEnd, end)
        }
        else {
            previousEnd = end
        }
    }
    return removal
}

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

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).

If we don't keep the interval with the smaller end time, it leads to WA for the following case:

[1, 2], [2, 3], [1, 3]

// Sort by `start` time, iterate each interval
// WA
[1, 2]
[1, 3], previous = 2
Overlapping with previous: 2, remove = 1
[2, 3], previous = 3
Overlapping with previous: 3, remove = 2

// Correct
// It should be 1 to remove if we keep track of the smaller `end` time.
[1, 2]
[1, 3], previous = 2
Overlapping with previous: 2, remove = 1
[2, 3], previous = 2 // The difference is here
Non-Overlapping, previous: 3

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

435. Non-overlapping Intervals

Greedy

Sorted By `end`

Sorted By `start`

Dry Run

FilesExpand file tree

435.non-overlapping-intervals.md

Latest commit

History

435.non-overlapping-intervals.md

File metadata and controls

435. Non-overlapping Intervals

Greedy

Sorted By end

Sorted By start

Dry Run

Sorted By `end`

Sorted By `start`