1288. Remove Covered Intervals

Given an array intervals where $intervals[i]=[l_i,r_i]$ represent the interval $[l_i,r_i)$, remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.
 

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• $0<=li<ri<=10^5$
• All the given intervals are unique.

From: LeetCode
Link: 1288. Remove Covered Intervals

---

Solution:

Ideas:

Sort by start ascending and end descending, then count intervals whose right endpoint is greater than every previous right endpoint.

Code:

#include <stdlib.h>

static int compare(const void* a, const void* b) {
    int* intervalA = *(int**)a;
    int* intervalB = *(int**)b;

    // Sort left endpoint ascending.
    if (intervalA[0] != intervalB[0]) {
        return intervalA[0] - intervalB[0];
    }

    // For equal left endpoints, sort right endpoint descending.
    return intervalB[1] - intervalA[1];
}

int removeCoveredIntervals(int** intervals, int intervalsSize,
                           int* intervalsColSize) {
    (void)intervalsColSize;

    qsort(intervals, intervalsSize, sizeof(int*), compare);

    int remaining = 0;
    int maxRight = -1;

    for (int i = 0; i < intervalsSize; i++) {
        if (intervals[i][1] > maxRight) {
            remaining++;
            maxRight = intervals[i][1];
        }
    }

    return remaining;
}