Vultr DocsLatest Content

Remove Covered Intervals

Updated on 24 June, 2025
Remove Covered Intervals header image

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

  • C++
  • Java
cpp 
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;
  }
};

The given C++ solution focuses on analyzing a list of intervals and counting the number of intervals that are not covered by other intervals. The goal is to determine how many intervals remain after removing those that are entirely covered by others.

Solution Approach:

  • First, the intervals are sorted based on their starting point. If two intervals have the same starting point, the one with the longer duration (or later end point) is considered first. This sorting facilitates the later step of determining coverage between consecutive intervals.

  • Initialize totalCount to count the non-overlapping intervals and lastCoveredEnd to keep track of where the last considered interval ends.

  • Iterate through each interval in the sorted list:

    • Check if the end point of the current interval is greater than lastCoveredEnd. If true, this interval is not covered by any prior interval and should be counted as a non-overlapping interval.
    • Update lastCoveredEnd to the end point of the current interval when it extends beyond the last recorded end point.

  • The function finally returns totalCount, which reflects the number of non-covered intervals in the original list.

This method ensures efficient coverage check by first sorting the intervals and then comparing each interval's end with the highest end point found so far. The algorithm is optimized for both time and space due to its linear pass through the sorted intervals and constant space overhead.

java 
class Solution {
  public int deleteCoveredIntervals(int[][] ranges) {
    Arrays.sort(ranges, new Comparator<int[]>() {
      @Override
      public int compare(int[] a, int[] b) {
        if (a[0] == b[0]) {
          return b[1] - a[1];
        }
        return a[0] - b[0];
      }
    });

    int total = 0;
    int lastEnd = 0;
    for (int[] interval : ranges) {
      int currentEnd = interval[1];
      if (lastEnd < currentEnd) {
        total++;
        lastEnd = currentEnd;
      }
    }
    return total;
  }
}

To solve the problem of removing covered intervals in Java, follow these outlined steps, which explain the given code to tackle the task effectively:

  1. Sort the Intervals: Begin by sorting the array of intervals based on their starting points. If two intervals have the same starting point, sort them based on their ending point in descending order. This ordering ensures that any interval potentially covered by another will come immediately after it.

  2. Initialize Variables: Set up two variables. One will track the total number of non-covered intervals (total), initialized to 0. The other (lastEnd) will keep track of the end of the most recently added interval to the set of non-covered intervals, initially set to 0.

  3. Iterate Through Intervals: Loop through the sorted intervals and use a condition to check if the current interval is not covered by the interval that was most recently added to the set of non-covered intervals. An interval is considered covered if its end is less than or equal to lastEnd.

  4. Update Variables: For each non-covered interval, increment total by one and update lastEnd to the end of the current interval.

  5. Return Result: After iterating through all the intervals, return total which now contains the count of all non-covered intervals.

The implemented method ensures efficiency and clarity, making it easier to manage and understand the process of filtering out the covered intervals.

Comments

No comments yet.