Problem of The Day: Non-overlapping Intervals

1 min read 295 words

Problem Statement

leetcode problem link

Solution [Accepted]

trick: want to maximize the number of intervals that are not overlapping. We need to pick the intervals that end early.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[1])
        print(intervals)
        res = 0
        k = float('-inf')
        for start, end in intervals:
            if start >= k:
                k = end
            else:
                res += 1
        return res

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1] - b[1]);
        int k = int.MinValue;
        int res = 0;
        foreach(int[] interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (k <= start) 
            {
                k = end;
            }
            else 
            {
                res += 1;
            }
        }
        return res;
    }
}s