“This is the 28th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

You are given a list of intervals and are asked to delete the intervals covered by other intervals in the list.

Only when c <= a and B <= d do we consider the interval [a,b) covered by the interval [c,d).

After all the deletions are complete, return the number of remaining ranges in the list.

Example:

Input: intervals = [[1,4],[3,6],[2,8]] output: 2 explanation: the interval [3,6] was overwritten by the interval [2,8], so it was deleted.

Tip:

  • 1 <= intervals.length <= 1000
  • 0 <= intervals[i][0] < intervals[i][1] <= 10^5
  • For all I! [j]. = intervals[j]
Analysis of the

After understanding the meaning of the question, we can find that the so-called deletion can directly replace the small intervals with the large intervals. When using the sorting, we can order the intervals directly according to the intervals[I][0]. If they are equal, the large intervals[I][1] come first.

Solution 1: Sort

Thinking: we first of all ascending order interval according to the left endpoint, if the left endpoint is the same, according to the right endpoint ascending order, so if you have covered, must be behind the front cover, for each interval, judging its behind how many elements of the right endpoint is less than the current element with the right endpoint, and subtract from the range of the total number

var removeCoveredIntervals = function(intervals) {
    intervals.sort((a,b) = > {
        if(a[0] == b[0]) {return b[1] - a[1];
        }else{
            return a[0]- b[0]; }})let right = intervals[0] [1],
        res = 0;
    for(let i = 1; i < intervals.length; i++){
        if(right >= intervals[i][1]){
            res++;
        }
        else if(right >= intervals[i][0] && right < intervals[i][1]){
            right = intervals[i][1];
        }
        else{
            right = intervals[i][1]; }}return intervals.length - res;
};
Copy the code
Solution 2: Dual Pointers

We can also use a double pointer to move the first and last Pointers. Whenever we move the first and last Pointers, we can delete the current element until the two Pointers are opposite.

var removeCoveredIntervals = function(intervals) {
    let { length } = intervals;
    for(let i = 0, j = length - 1; i < length; i++){
        while(j >= 0&& j ! = i){if(intervals[j][0] <= intervals[i][0] && intervals[j][1] >= intervals[i][1]){
                intervals.splice(i, 1);
                i -= 1;
                length = intervals.length;
                break;
            }else if(intervals[j][0] >= intervals[i][0] && intervals[j][1] <= intervals[i][1]){
                intervals.splice(j, 1);
                length = intervals.length;
            }
            j--;
        }
        j = length - 1;
    }
    return intervals.length;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤