38. Remove Covered Intervals

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), 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

Solution: (Sorting)

class Solution
{
public:
    static bool comparator(vector<int> &a, vector<int> &b)
    {
        if (a[0] == b[0])
        {
            return a[1] > b[1];
        }

        return a[0] < b[0];
    }

    int removeCoveredIntervals(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end(), comparator);

        int pos = 0, count = 0;

        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] >= intervals[pos][0] && intervals[i][1] <= intervals[pos][1])
            {
                count++;
                intervals[pos][0] = min(intervals[pos][0], intervals[i][0]);
                intervals[pos][1] = max(intervals[pos][1], intervals[i][1]);
            }
            else
            {
                pos = i;
            }
        }

        return intervals.size() - count;
    }
};

Time Complexity: O(n log n)