Problem of The Day: Non-overlapping Intervals

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => {
            if (a == null && b == null) return 0;
            if (a == null) return -1;
            if (b == null) return 1;
            return a[0].CompareTo(b[0]);
        });
        int res = 0;
        int prev_end = int.MinValue; // FIX: Use int.MinValue to handle full constraint range
        foreach (int[] interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (prev_end > start) { // FIX: Only check if current start is before previous end (overlap)
                res += 1;
                // FIX: Keep the interval with the earlier end time to minimize future overlaps
                prev_end = Math.Min(prev_end, end);
            } else {
                prev_end = end;
            }
        }
        return res;
    }
}

Editorial

Approach: Greedy

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: x[1])
        ans = 0
        k = -inf

        for x, y in intervals:
            if x >= k:
                # Case 1
                k = y
            else:
                # Case 2
                ans += 1

        return ans