Leetcode 1288: Remove Covered Intervals

Input: The input consists of an array of intervals where each interval is represented as [li, ri].

Example: Input: [[1,5], [2,6], [3,7], [4,8]]

Constraints:

• 1 <= intervals.length <= 1000

• intervals[i].length == 2

• 0 <= li < ri <= 10^5

• All the given intervals are unique.

Output: The function should return the number of remaining intervals after removing all covered intervals.

Example: Output: 2

Constraints:

• The input intervals are unique.

Goal: The goal is to remove intervals that are covered by other intervals and return the count of the remaining intervals.

Steps:

• Sort the intervals based on their starting value.

• Iterate through the sorted intervals and keep track of the rightmost end of the previous interval.

• For each new interval, if its end is less than or equal to the rightmost end, it is covered by the previous interval and can be discarded.

• Otherwise, update the rightmost end and increment the count of remaining intervals.

Goal: The constraints ensure that the intervals are unique and the array length is manageable.

Steps:

• The number of intervals is between 1 and 1000.

• Each interval is represented by two integers, where 0 <= li < ri <= 10^5.

Assumptions:

• Intervals are unique and no two intervals are identical.

• Input: Input: [[1,5], [2,6], [3,7], [4,8]]

• Explanation: Intervals `[2,6]`, `[3,7]`, and `[4,8]` are covered by `[1,5]`. The remaining intervals are `[1,5]` and `[4,8]`.

Approach: To solve this problem, we will sort the intervals based on their start value and then remove the intervals that are covered by others.

Observations:

• Sorting the intervals first helps us easily compare each interval to the previous one to check for coverage.

• We need to iterate through the intervals and keep track of the rightmost end seen so far to determine if the current interval is covered.

Steps:

• Sort the intervals based on the starting value of each interval.

• Initialize variables for the rightmost end and the count of remaining intervals.

• Loop through the sorted intervals and check if the current interval is covered by the previous one.

• If not, update the rightmost end and increment the count.

Empty Inputs:

• An empty array will never occur since the length of the intervals is guaranteed to be at least 1.

Large Inputs:

• The solution should handle arrays with up to 1000 intervals efficiently.

Special Values:

• If all intervals are distinct and no interval is covered, the output will be the total number of intervals.

Constraints:

• Since all intervals are unique, there will be no duplicate intervals to handle.

int removeCoveredIntervals(vector<vector<int>>& ivl) {
    sort(ivl.begin(), ivl.end());
    int res = 0, left = -1, right = -1;
    
    for(auto p: ivl) {
        if(left < p[0] && right < p[1]) {
            res++;
            left = p[0];
        }
        right = max(p[1], right);
    }
    
    return res;
}

1 : Function Definition

int removeCoveredIntervals(vector<vector<int>>& ivl) {

Defines the function to compute the count of intervals that are not covered by others.

2 : Sorting

    sort(ivl.begin(), ivl.end());

Sorts the intervals by their starting point and, in case of ties, by their ending point.

3 : Variable Initialization

    int res = 0, left = -1, right = -1;

Initializes variables to keep track of the count of non-covered intervals and boundaries.

4 : Loop Start

    for(auto p: ivl) {

Iterates through each interval in the sorted list.

5 : Condition Check

        if(left < p[0] && right < p[1]) {

Checks if the current interval is not covered by the previous interval.

6 : Increment Counter

            res++;

Increments the counter for non-covered intervals.

7 : Update Left Boundary

            left = p[0];

Updates the left boundary to the starting point of the current interval.

8 : Update Right Boundary

        right = max(p[1], right);

Updates the right boundary to the maximum of the current interval's end or the previous boundary.

9 : Return Result

    return res;

Returns the count of non-covered intervals.

Best Case: O(n log n) - Sorting the intervals takes O(n log n), where n is the number of intervals.

Average Case: O(n log n) - The sorting step dominates the time complexity.

Worst Case: O(n log n) - In the worst case, we need to sort the intervals and iterate through them once.

Description: The time complexity is O(n log n) because of the sorting step.

Best Case: O(n) - In the best case, we still need space for the sorted intervals.

Worst Case: O(n) - The space complexity is O(n) in the worst case if we store the sorted intervals.

Description: The space complexity is O(n) to store the sorted intervals.

Leetcode 1288: Remove Covered Intervals

Explore →