1288. Remove Covered Intervals


Problem Description

The problem presents a scenario in which you're given a list of intervals, with each interval represented as a pair of integers [start, end). The notation [start, end) signifies that the interval includes start and goes up to but does not include end. The goal is to remove intervals that are "covered" by other intervals. An interval [a, b) is considered covered by another interval [c, d) if both c <= a and b <= d. In simple terms, if one interval lies completely within the boundary of another, the inner interval is said to be covered by the outer interval. Your task is to find out how many intervals remain after removing all the covered intervals.

Intuition

The intuitive approach to solving this problem involves checking each interval against all others to see if it is covered by any. However, this would be inefficient, particularly for large lists of intervals. Thus, the key to an efficient solution is to sort the intervals in a way that makes it easier to identify and remove the covered intervals.

By sorting the intervals first by their start times and then by their end times in descending order, we line up intervals in such a way that once we find an interval not covered by the previous one, none of the following intervals will cover it either. This sorting strategy allows us to only compare each interval with the last one that wasn't removed.

With the sorted list, we iterate through the intervals, where the main idea is to compare the current interval's end with the previous interval's end. If the current end is greater, this interval isn't covered by the previous interval. We count this interval, and it becomes the new previous interval for subsequent comparisons. If the current end is not greater, it means this interval is covered by the previous interval, and we do not count it and proceed to the next interval. After checking all intervals, the count cnt gives the number of intervals that remain.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The solution makes use of a greedy algorithm approach, where we aim to remove the minimal number of intervals by keeping the ones that aren't covered by any other. Let's walk through the solution approach along with the algorithms, data structures, or patterns used:

  1. Sorting: We begin by sorting the intervals list using a custom sort key. This key sorts the intervals primarily by their start times in ascending order. If two intervals have the same start time, we sort them by their end times in descending order. This ensures that we have the longer intervals earlier if the start times are the same, making it easier to identify covered intervals.

  2. Initializing Counters: After sorting, we initialize our count cnt to 1. This is because we consider the first interval as not being covered by any previous one, as there are no previous intervals yet. We also initialize pre to keep track of the last interval that was not covered by the one before it.

  3. Iterating Through Intervals: We loop through the sorted intervals starting from the second one. At each iteration, we compare the current interval's end time (e[1]) with the end time of pre (pre[1]):

    • If pre[1] (previous interval's end time) is less than e[1] (current interval's end time), it indicates that the current interval is not completely covered by pre. Hence, we increment our count cnt and update pre to the current interval.

    • If pre[1] is greater than or equal to e[1], the current interval is covered by pre, and we don't increment cnt.

  4. Return the Result: After iterating through all intervals, cnt holds the count of intervals that remain after removing all that are covered by another interval.

It's important to understand that by sorting the intervals first by starting time and then by the ending time (in opposite order), we limit the comparison to only the previous interval and the current one in the loop. This greatly reduces the number of comparisons needed, resulting in a more efficient algorithm.

Below is the reference code implementation based on this approach:

1class Solution:
2    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
3        # Sort intervals by start time, and then by end time in descending order
4        intervals.sort(key=lambda x: (x[0], -x[1]))
5      
6        cnt, pre = 1, intervals[0]  # Initialize the counter and the previous interval tracker
7      
8        # Iterate through each interval in the sorted list
9        for e in intervals[1:]:
10            # If the current interval's end time is greater than the previous', it's not covered
11            if pre[1] < e[1]:
12                cnt += 1    # Increment the counter, as this interval isn't covered
13                pre = e     # Update the 'pre' interval tracker to the current interval
14      
15        return cnt  # Return the final count of non-covered intervals

With the combination of a clever sorting strategy and a single loop, this code neatly solves the problem in an efficient manner.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Example Walkthrough

Let's go through a small example to illustrate the solution approach described.

Suppose we have a list of intervals: [[1,4), [2,3), [3,6)].

Following our solution approach:

  1. Sorting: Applying our custom sort, the list is sorted by start times in ascending order, and for those with the same start time, by end times in descending order. But since all our example intervals have different start times, we only need to sort by the first element:

Sorted list: [[1,4), [2,3), [3,6)]

  1. Initializing Counters: We initialize our count cnt to 1, assuming the first interval [1,4) is not covered. We also initialize pre with this interval.

  2. Iterating Through Intervals:

    • We first compare [1,4) with [2,3). Here, pre[1] is 4 and e[1] is 3. Since pre[1] >= e[1], we find that [2,3) is covered by [1,4) and thus, we do not increment cnt.

    • Next, we compare [1,4) with [3,6). Here, pre[1] is 4 and e[1] is 6. Since pre[1] < e[1], we find that [3,6) is not covered by [1,4). So, we increment cnt to 2 and update pre to [3,6).

  3. Return the Result: Having finished iterating through the intervals, we find that the count cnt is 2, which means there are two intervals that remain after removing all that are covered: [[1,4), [3,6)].

This example walk-through demonstrates the efficiency of the algorithm by effectively reducing the number of necessary comparisons and clearly exhibiting how the sorting step greatly simplifies the process of identifying covered intervals.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Python Solution

1from typing import List
2
3class Solution:
4    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
5        # Sort intervals based on the start time; in case of a tie, sort by end time in descending order
6        intervals.sort(key=lambda interval: (interval[0], -interval[1]))
7      
8        # Initialize count of non-covered intervals to 1, as the first one can never be covered by others
9        non_covered_count = 1
10        # The first interval is the current reference for comparison
11        previous_interval = intervals[0]
12      
13        # Iterate over the sorted intervals starting from the second interval
14        for current_interval in intervals[1:]:
15            # If the end of the current interval is greater than the end of the previous interval,
16            # it's not covered, and we should update the count and reference interval
17            if previous_interval[1] < current_interval[1]:
18                non_covered_count += 1
19                previous_interval = current_interval
20              
21        # Return the final count of non-covered intervals
22        return non_covered_count
23

Java Solution

1class Solution {
2    public int removeCoveredIntervals(int[][] intervals) {
3        // Sort the intervals. First by the start in ascending order.
4        // If the starts are equal, sort by the end in descending order.
5        Arrays.sort(intervals, (a, b) -> {
6            if (a[0] == b[0]) {
7                return b[1] - a[1];
8            } else {
9                return a[0] - b[0];
10            }
11        });
12
13        // Initialize the previous interval as the first interval
14        int[] previousInterval = intervals[0];
15        // Count the first interval
16        int count = 1;
17
18        // Iterate through all intervals starting from the second one
19        for (int i = 1; i < intervals.length; ++i) {
20            // If the current interval's end is greater than the previous interval's end,
21            // it means the current interval is not covered by the previous interval.
22            if (previousInterval[1] < intervals[i][1]) {
23                // Increment the count of non-covered intervals.
24                ++count;
25                // Update the previous interval to the current interval.
26                previousInterval = intervals[i];
27            }
28            // If the current interval's end is not greater than the previous interval's end,
29            // it's covered by the previous interval and we do nothing.
30        }
31
32        // Return the number of non-covered intervals
33        return count;
34    }
35}
36

C++ Solution

1#include <vector>
2#include <algorithm> // Include algorithm header for std::sort
3
4// Definition for the Solution class with removeCoveredIntervals method
5class Solution {
6public:
7    int removeCoveredIntervals(vector<vector<int>>& intervals) {
8        // Sort the intervals. First by the start time, and if those are equal, by the
9        // end time in descending order (to have the longer intervals come first).
10        sort(intervals.begin(), intervals.end(), [](const vector<int>& intervalA, const vector<int>& intervalB) {
11            if (intervalA[0] == intervalB[0]) // If the start times are the same
12                return intervalB[1] < intervalA[1]; // Sort by end time in descending order
13            return intervalA[0] < intervalB[0]; // Otherwise sort by start time
14        });
15
16        int countNotCovered = 1; // Initialize count of intervals not covered by others.
17        vector<int> previousInterval = intervals[0]; // Store the first interval as the initial previous interval
18
19        // Iterate through the intervals starting from the second
20        for (int i = 1; i < intervals.size(); ++i) {
21            // If the current interval is not covered by the previous interval
22            if (previousInterval[1] < intervals[i][1]) {
23                ++countNotCovered; // Increment count as this interval is not covered
24                previousInterval = intervals[i]; // Update the previous interval to current interval
25            }
26        }
27
28        // Return the count of intervals that are not covered by other intervals
29        return countNotCovered;
30    }
31};
32

Typescript Solution

1// You might need to install the required type definitions for running this code in a TypeScript environment.
2
3// Importing necessary functionalities from standard libraries
4import { sort } from 'algorithm';
5
6// Interval type definition for better type clarity
7type Interval = [number, number];
8
9// A function that sorts the intervals based on certain criteria
10function sortIntervals(intervals: Interval[]): Interval[] {
11    return intervals.sort((intervalA, intervalB) => {
12        if (intervalA[0] === intervalB[0]) // If start times are the same
13            return intervalB[1] - intervalA[1]; // Sort by end time in descending order
14        return intervalA[0] - intervalB[0]; // Otherwise sort by start time
15    });
16}
17
18// Function to remove covered intervals
19function removeCoveredIntervals(intervals: Interval[]): number {
20    // Sort the intervals using the defined sorting function
21    const sortedIntervals = sortIntervals(intervals);
22
23    let countNotCovered = 1; // Initialize count of intervals not covered by others
24    let previousInterval = sortedIntervals[0]; // Store the first interval as the initial previous interval
25
26    // Iterate through the sorted intervals starting from the second one
27    for (let i = 1; i < sortedIntervals.length; i++) {
28        // If the current interval is not covered by the previous interval
29        if (previousInterval[1] < sortedIntervals[i][1]) {
30            countNotCovered++; // Increment count as this interval is not covered
31            previousInterval = sortedIntervals[i]; // Update the previous interval to current interval
32        }
33    }
34
35    // Return the number of intervals that are not covered by other intervals
36    return countNotCovered;
37}
38
Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

The time complexity of the code is dominated by two operations: the sorting of the intervals and the single pass through the sorted list.

  1. The sort() function in Python uses the Timsort algorithm, which has a time complexity of O(n log n) where n is the number of intervals.
  2. After sorting, the code performs a single pass through the list to count the number of non-covered intervals, which has a time complexity of O(n).

Combining these two steps, the overall time complexity is O(n log n + n). Simplified, it remains O(n log n) because the n log n term is dominant.

Space Complexity

The space complexity refers to the amount of extra space or temporary storage that an algorithm requires.

  1. Sorting the list is done in-place, which means it doesn't require additional space proportional to the input size. Therefore, the space complexity due to sorting is constant, O(1).
  2. Aside from the sorted list, the algorithm only uses a fixed number of variables (cnt, pre, and e) which also take up constant space.

Hence, the overall space complexity is O(1), because no additional space that scales with the size of the input is used.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫