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.
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:
-
Sorting: We begin by sorting the
intervals
list using a custom sort key. This key sorts the intervals primarily by theirstart
times in ascending order. If two intervals have the samestart
time, we sort them by theirend
times in descending order. This ensures that we have the longer intervals earlier if thestart
times are the same, making it easier to identify covered intervals. -
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 initializepre
to keep track of the last interval that was not covered by the one before it. -
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 theend
time ofpre
(pre[1]
):-
If
pre[1]
(previous interval's end time) is less thane[1]
(current interval's end time), it indicates that the current interval is not completely covered bypre
. Hence, we increment our countcnt
and updatepre
to the current interval. -
If
pre[1]
is greater than or equal toe[1]
, the current interval is covered bypre
, and we don't incrementcnt
.
-
-
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:
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
# Sort intervals by start time, and then by end time in descending order
intervals.sort(key=lambda x: (x[0], -x[1]))
cnt, pre = 1, intervals[0] # Initialize the counter and the previous interval tracker
# Iterate through each interval in the sorted list
for e in intervals[1:]:
# If the current interval's end time is greater than the previous', it's not covered
if pre[1] < e[1]:
cnt += 1 # Increment the counter, as this interval isn't covered
pre = e # Update the 'pre' interval tracker to the current interval
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
- Sorting: Applying our custom sort, the list is sorted by
start
times in ascending order, and for those with the samestart
time, byend
times in descending order. But since all our example intervals have differentstart
times, we only need to sort by the first element:
Sorted list: [[1,4), [2,3), [3,6)]
-
Initializing Counters: We initialize our count
cnt
to 1, assuming the first interval[1,4)
is not covered. We also initializepre
with this interval. -
Iterating Through Intervals:
-
We first compare
[1,4)
with[2,3)
. Here,pre[1]
is 4 ande[1]
is 3. Sincepre[1] >= e[1]
, we find that[2,3)
is covered by[1,4)
and thus, we do not incrementcnt
. -
Next, we compare
[1,4)
with[3,6)
. Here,pre[1]
is 4 ande[1]
is 6. Sincepre[1] < e[1]
, we find that[3,6)
is not covered by[1,4)
. So, we incrementcnt
to 2 and updatepre
to[3,6)
.
-
-
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.
Solution Implementation
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
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
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
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
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.
- The
sort()
function in Python uses the Timsort algorithm, which has a time complexity ofO(n log n)
wheren
is the number of intervals. - 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.
- 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)
. - Aside from the sorted list, the algorithm only uses a fixed number of variables (
cnt
,pre
, ande
) 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 using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!