LeetCode from inefficient to efficient, click

I. Title Description:

Topic request

Given a set of intervals, find the minimum number of intervals to remove so that the remaining intervals do not overlap.

Note that the end of the interval can always be thought of as greater than its beginning. The boundaries of the intervals [1,2] and [2,3] “touch” each other, but do not overlap each other.

Source: LeetCode

The sample

Input: [[1, 2], [2, 3], [3, 4], [1, 3]] output: 1: after removing [1, 3], the rest of the band didn't overlap.Copy the code

Ii. Analysis of Ideas:

The difficulty of this problem lies in the need to detect the left and right boundaries. At first, I thought of doing it as DP. Later, I thought if I could fix one boundary and judge the other boundary, but it was not very good, because the right boundary of A might touch the left boundary of B. But if sorted on the left border, adjacent to interval is only have the border crossing with the a b left border/disjoint, two cases, when an intersection collision cannot exist together, the two interval noticed that no matter which will not affect retention before the interval, so this time as long as the small reserves the right boundary.

Iii. AC Code:

// 16ms 9mb
int eraseOverlapIntervals(vector<vector<int>> &intervals)
{
    if (intervals.size() = =0)
        return 0;
    sort(intervals.begin(), intervals.end(), [](vector<int> &x, vector<int> &y) {
        return x[0] < y[0];
    });
    int flag = intervals[0] [1];
    int count = 0;
    // Put the first one in and try from the second one
    for (int i = 1; i < intervals.size(a); i++) {// If a collision occurs, leave the one with the smaller end unchanged, and fix the flag
        if (intervals[i][0] < flag)
        {
            flag = min(flag, intervals[i][1]);
            count++;
        }
        else
        {
            
            flag = intervals[i][1]; }}return count;
}
Copy the code

Iv. Summary:

Using sorting to reduce the number of subsequent judgments is a very effective strategy when there are too many judgments.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign