LeetCode //C - 435. Non-overlapping Intervals-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 435. Non-overlapping Intervals。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = $start_i, end_i]$ , return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don’t need to remove any of the intervals since they’re already non-overlapping.

Constraints:

$1 <= intervals.length <= 10^5$
intervals[i].length == 2
$5 * 10^4 <= starti < endi <= 5 * 10^4$

From: LeetCode
Link: 435. Non-overlapping Intervals

Solution:

Ideas：

Sorting: The intervals are first sorted based on their end times using qsort and a custom comparator. Sorting by end time helps in selecting the intervals that finish the earliest, reducing the chance of future overlaps.
Greedy Selection: We then iterate through the sorted intervals. The variable lastEnd keeps track of the end time of the last interval that was added to our timeline. For each interval, if its start time is less than lastEnd, it means the interval overlaps with the previous one, and we need to remove it. Otherwise, we update lastEnd to the current interval’s end time.
Counting Removals: The variable removeCount keeps track of the number of intervals that need to be removed. This is incremented each time we find an overlapping interval.文章来源地址https://www.toymoban.com/news/detail-834296.html

Caode:

// Comparator function for qsort
int compare(const void* a, const void* b) {
    int* intervalA = *(int**)a;
    int* intervalB = *(int**)b;
    return intervalA[1] - intervalB[1];
}

int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
    // Sort the intervals based on their end times
    qsort(intervals, intervalsSize, sizeof(int*), compare);
    
    int removeCount = 0; // Count of intervals to remove
    int lastEnd = intervals[0][1]; // End time of the last interval considered in the timeline

    // Iterate through the intervals starting from the second one
    for (int i = 1; i < intervalsSize; i++) {
        // If the current interval starts before the last one ends, it overlaps
        if (intervals[i][0] < lastEnd) {
            removeCount++; // Need to remove an interval
        } else {
            // No overlap, update the end time to the current interval's end
            lastEnd = intervals[i][1];
        }
    }
    
    return removeCount; // Number of intervals that need to be removed
}