Remove Covered Intervals

Problem Statement

The problem presents us with an array of intervals, with each interval defined by a pair [li, ri). Here, li and ri represent the inclusive start and exclusive end of the interval respectively. Our task is to identify how many of such intervals are not covered by any other interval in the list. An interval [a, b) is said to be covered by another interval [c, d) if c is less than or equal to a, and b is less than or equal to d. Ultimately, we need to return the count of intervals that remain after removing all covered intervals.

Examples

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 <= 105
• All the given intervals are unique.

Approach and Intuition

The provided examples help in understanding the problem more clearly:

1. Example 1:
   For intervals [[1,4], [3,6], [2,8]]:

   • The interval [3,6] is wholly within [2,8]. Hence, [3,6] is covered and removed.
   • The intervals [1,4] and [2,8] remain, leading to an output of 2.

2. Example 2:
   For intervals [[1,4], [2,3]]:

   • The interval [2,3] lies completely within [1,4], so [2,3] is covered and removed.
   • Only the interval [1,4] remains, leading to an output of 1.

From the examples, we deduce the general approach:

1. Sorting: Start by sorting the intervals based on their starting point li. In case of a tie, prioritize intervals by the ending point ri in descending order. This helps us in having a structured way to identify covering intervals.

2. Comparison Algorithm: Use a double pointer or iteration technique:

   • Initialize a variable, say maxEnd, to keep track of the farthest point an interval has covered.
   • Traverse through the sorted intervals:
     • If an interval's ending, ri, is less than maxEnd, it's entirely covered by the previously considered intervals, and hence can be discarded.
     • Update maxEnd whenever you encounter an interval that extends it.

3. Count the Uncovered Intervals: Every time an interval is considered and isn't covered, increment a counter.

This approach assesses each interval at most once in the sorted order, ensuring an efficient solution. The constraints allow tying this approach feasibly, given that up to 1000 intervals can be processed within acceptable time frames.

Solutions

class Solution {
  public:
  int countNonOverlappingIntervals(vector<vector<int>>& intervalList) {
    // Sort intervals to manage overlaps
    sort(begin(intervalList), end(intervalList),
      [](const vector<int> &first, const vector<int> &second) {
      return first[0] == second[0] ? second[1] < first[1] : first[0] < second[0];
    });
    
    int totalCount = 0;
    int lastCoveredEnd = 0, currentEnd;
    for (const auto &interval : intervalList) {
      currentEnd = interval[1];
      if (lastCoveredEnd < currentEnd) {
        ++totalCount;  
        lastCoveredEnd = currentEnd;
      }
    }
    return totalCount;
  }
};