Leetcode Non-overlapping intervals problem solution

YASH PAL,

In this Leetcode Non-overlapping intervals problem solution we have Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Leetcode Non-overlapping intervals problem solution

Problem solution in Python.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[0])
        n=len(intervals)
        i=0
        j=1
        count=0
        while j<n:
            if intervals[i][1]<=intervals[j][0]: #Non overlapping
                i=j
                j+=1
            elif intervals[i][1]<=intervals[j][1]: #partial overlapping
                j+=1
                count+=1
            elif intervals[i][1]>=intervals[j][1]: #full overalapping
                i=j
                count+=1
                j+=1
        return count

Problem solution in Java.

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        LinkedList<int[]> link = new LinkedList<>();
        
        for (int i = 0; i < intervals.length; i++) {
            if (link.isEmpty() || link.getLast()[1] <= intervals[i][0]) {
                link.add(intervals[i]);
            }
        }
        return intervals.length - link.size();
    }
}

Problem solution in C++.

class Solution {
public:
    int eraseOverlapIntervals(vector<Interval>& intervals) {
        std::sort(intervals.begin(), intervals.end(), 
                    [](const Interval& lhs, const Interval& rhs) {
                        if (lhs.end != rhs.end) {
                            return lhs.end < rhs.end;
                        } else {
                            return lhs.start > rhs.start;
                        }
                    });
                    
        int n = intervals.size(), lastIdx = 0; 
        int result = 0;
        for (int i = 1; i < n; i++) {
            if (intervals[i].start < intervals[lastIdx].end) {
                result++;
            } else {
                lastIdx = i;
            }
        }
        return result;
    }
};

Problem solution in C.

int eraseOverlapIntervals(struct Interval* intervals, int intervalsSize) {
    int cmp(const void*a,const void*b)
    {
        return (*(struct Interval *)a).end -(*(struct Interval *)b).end ;
    }
    qsort(intervals, intervalsSize, sizeof(intervals[0]), cmp);
    int i = 0;
    int j = i + 1;
    int num = 0;
    while(i < intervalsSize - 1 && j < intervalsSize){
        if(intervals[j].start<intervals[i].end){
            num++;
        }else{
            i = j;
        }
        j++;
    }
    return num;
}

coding problems