SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem requires us to find the minimum number of intervals that need to be removed to ensure that no intervals overlap. We are given a list of intervals, where each interval is represented as a pair of start and end times. The goal is to remove the fewest possible intervals so that the remaining intervals do not overlap.

Intuition

To minimize the number of intervals to remove, we should prioritize keeping intervals that end the earliest. By doing so, we leave more space for subsequent intervals, reducing the likelihood of overlap. Therefore, sorting the intervals by their end times will help us identify and keep the optimal intervals, while discarding the rest.

Approach

1. Sort the Intervals: First, we sort the intervals based on their end times. This allows us to focus on intervals that end the earliest, maximizing the remaining space for subsequent intervals.

2. Iterate and Compare: Start iterating through the sorted intervals. Compare the start time of the current interval with the end time of the previous interval.

   • If the current interval's start time is less than the previous interval's end time, an overlap occurs, and we increase the count of intervals to remove.
   • If no overlap occurs, update the previous interval's end time to the current interval's end time.

3. Return the Result: The total number of intervals that need to be removed is stored in the result variable.

Complexity

Time Complexity:

O(n log n) due to the sorting step, where n is the number of intervals. The subsequent iteration through the intervals is O(n), making the overall time complexity O(n log n).

Space Complexity:

O(1) since the sorting is done in place and only a constant amount of extra space is used.

Code

C++

class Solution {
public:
    int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[1] < b[1];
        });

        int res = 0;
        int prev_end = intervals[0][1];

        for (int i = 1; i < intervals.size(); ++i) {
            if (prev_end > intervals[i][0]) {
                ++res;
            } else {
                prev_end = intervals[i][1];
            }
        }

        return res;
    }
};

Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[1])
        
        res = 0
        prev_end = intervals[0][1]
        
        for i in range(1, len(intervals)):
            if prev_end > intervals[i][0]:
                res += 1
            else:
                prev_end = intervals[i][1]
        
        return res

Java

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

        int res = 0;
        int prevEnd = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (prevEnd > intervals[i][0]) {
                res++;
            } else {
                prevEnd = intervals[i][1];
            }
        }

        return res;
    }
}

JavaScript

var eraseOverlapIntervals = function (intervals) {

    let res = 0;
    intervals.sort((a, b) => a[1] - b[1]);
    let prev_end = intervals[0][1];

    for (let i = 1; i < intervals.length; i++) {

        if (prev_end > intervals[i][0]) {
            res++;

        } else {
            prev_end = intervals[i][1];
        }
    }
    return res;
};