This article records the important concepts and notes in the process of brushing the questions. If there is any infringement, please contact to delete.
Table of Contents
- 435. Non-overlapping intervals
- train of thought
- method 1
- Method 2: Left Sort
- Contact: 452. Detonate Balloons with Minimum Number of Arrows
435. No overlapping interval
Link to Links(opens new window)
Given a collection of intervals, find the minimum number of intervals that need to be removed such that the remaining intervals do not overlap.
Note: It can be considered that the end of an interval is always greater than its start. The boundaries of intervals [1,2] and [2,3] “touch” each other, but do not overlap.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ]
output: 1
Explanation: After removing [1,3], the remaining intervals do not overlap.
Example 2:
Input: [ [1,2], [1,2], [1,2] ]
output: 2
Explanation: You need to remove both [1,2] to make the remaining intervals non-overlapping.
Example 3:
Input: [ [1,2], [2,3] ]
output: 0
Explanation: You don’t need to remove any intervals, since they are already non-overlapping.
Thoughts
Method 1
Let me sort by the right boundary and record the number of non-intersecting intervals from left to right. Finally, subtract the number of non-intersection intervals from the total number of intervals to get the number of intervals that need to be removed. 
class Solution {<!-- -->
public:
// Sort by the right edge of the range
static bool cmp (const vector<int> & amp; a, const vector<int> & amp; b) {<!-- -->
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>> & intervals) {<!-- -->
if (intervals. size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 1; // record the number of non-intersection intervals
int end = intervals[0][1]; // record interval split point
for (int i = 1; i < intervals. size(); i ++ ) {<!-- -->
if (end <= intervals[i][0]) {<!-- -->
end = intervals[i][1];
count + + ;
}
}
return intervals. size() - count;
}
};
Time complexity: O(nlog n) with a quicksort?
Space complexity: O(n), there is a quick sort, and in the worst case (reverse order), n recursive calls are required. So it does require O(n) stack space
Method 2: Left Sort
Is it possible to sort on the left border?
It is also possible, but we just find the overlapping intervals directly for sorting on the left boundary, and count is the number of overlapping intervals recorded.
class Solution {<!-- -->
public:
static bool cmp (const vector<int> & amp; a, const vector<int> & amp; b) {<!-- -->
return a[0] < b[0]; // Change to left border sorting
}
int eraseOverlapIntervals(vector<vector<int>> & intervals) {<!-- -->
if (intervals. size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 0; // Note that this starts from 0, because it is an overlapping interval of records
int end = intervals[0][1]; // record interval split point
for (int i = 1; i < intervals. size(); i ++ ) {<!-- -->
if (intervals[i][0] >= end) end = intervals[i][1]; // no overlap
else {<!-- --> // Overlap: update the right boundary to the minimum value
end = min(end, intervals[i][1]);
count + + ;
}
}
return count;
}
};
In fact, the code can be simplified a bit, using intervals[i][1] instead of the end variable, just judging the overlap
class Solution {<!-- -->
public:
static bool cmp (const vector<int> & amp; a, const vector<int> & amp; b) {<!-- -->
return a[0] < b[0]; // Change to left border sorting
}
int eraseOverlapIntervals(vector<vector<int>> & intervals) {<!-- -->
if (intervals. size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 0; // Note that this starts from 0, because it is an overlapping interval of records
for (int i = 1; i < intervals. size(); i ++ ) {<!-- -->
if (intervals[i][0] < intervals[i - 1][1]) {<!-- --> //overlap
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
count + + ;
}
}
return count;
}
};
Contact: 452. Detonate balloon with minimum number of arrows
This question is actually very similar to 452. Use the least number of arrows to detonate the balloon (opens new window). The number of bows and arrows is equivalent to the number of non-crossing intervals. Just add An equal sign (think [0, 1] [1, 2] is not an adjacent interval), and then subtract the number of bows and arrows from the total number of intervals to be the number of intervals to be removed.
class Solution {<!-- -->
public:
// Sort by the right edge of the range
static bool cmp (const vector<int> & amp; a, const vector<int> & amp; b) {<!-- -->
return a[1] < b[1]; // right border sorting
}
int eraseOverlapIntervals(vector<vector<int>> & intervals) {<!-- -->
if (intervals. size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int result = 1; // points need at least one arrow if it is not empty
for (int i = 1; i < intervals. size(); i ++ ) {<!-- -->
if (intervals[i][0] >= intervals[i - 1][1]) {<!-- -->
result + + ; // needs an arrow
}
else {<!-- --> // balloon i and balloon i-1 next to each other
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // Update the minimum right boundary of overlapping balloons
}
}
return intervals. size() - result;
}
};
Here, sorting according to the left boundary or sorting according to the right boundary can be AC, and the principle is the same.
class Solution {<!-- -->
public:
// Sort by the left boundary of the range
static bool cmp (const vector<int> & amp; a, const vector<int> & amp; b) {<!-- -->
return a[0] < b[0]; // left border sorting
}
int eraseOverlapIntervals(vector<vector<int>> & intervals) {<!-- -->
if (intervals. size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int result = 1; // points need at least one arrow if it is not empty
for (int i = 1; i < intervals. size(); i ++ ) {<!-- -->
if (intervals[i][0] >= intervals[i - 1][1]) {<!-- -->
result + + ; // needs an arrow
}
else {<!-- --> // balloon i and balloon i-1 next to each other
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // Update the minimum right boundary of overlapping balloons
}
}
return intervals. size() - result;
}
};