435. Non-overlapping Intervals
Problem Description
The problem asks us to find the minimum number of intervals that need to be removed from a given list of time intervals to ensure that no two intervals overlap with each other. Intervals overlap when one interval starts before the other one ends. For example, if one interval is [1, 2]
and another is [2, 3]
, they do not overlap, but if the second interval is [1, 3]
, they do overlap because the first interval has not ended before the second one starts.
Our input is an array of intervals, where each interval is represented as a list with two elements, signifying the start and the end times. The output should be an integer that represents the minimum number of intervals that must be removed to eliminate all overlaps.
Intuition
The key intuition behind the solution lies in the greedy algorithm approach. A greedy algorithm makes the locally optimal choice at each stage with the hope of finding the global optimum. In the context of this problem, the greedy choice would be to always pick the interval that ends the earliest, because this would leave the most room for subsequent intervals.
Here is the thinking process for arriving at the solution:
- Sort the intervals based on their end times. This way, we encounter the intervals that finish earliest first and can thus make the greedy choice.
- Start with the first interval, considering it as non-overlapping by default, and make a note of its end time.
- Iterate through the subsequent intervals:
- If the start time of the current interval is not less than the end time of the last non-overlapping interval, it means this interval does not overlap with the previously considered intervals. We can then update our last known end time to be the end time of the current interval.
- If the start time is less than the last known end time, an overlap occurs, and we must choose to remove an interval. Following the greedy approach, we keep the interval with the earlier end time and remove the other by incrementing our answer (the number of intervals to remove).
By following these steps and always choosing the interval that finishes earliest, we ensure that we take up the least possible space on the timeline for each interval, and therefore maximize the number of intervals we can include without overlapping.
Learn more about Greedy, Dynamic Programming and Sorting patterns.
Solution Approach
The provided solution follows the greedy strategy mentioned in the reference solution approach. Let's discuss how the solution is implemented in more detail:
-
Sorting Intervals: The input list of intervals is sorted based on the end times of the intervals. This is done using Python's
sort
function with a lambda function as the key that retrieves the end timex[1]
from each intervalx
.intervals.sort(key=lambda x: x[1])
Sorting the intervals by their end times allows us to apply the greedy algorithm effectively.
-
Initializing Variables: Two variables are initialized:
ans
: set to0
, it keeps count of the number of intervals we need to remove.t
: set to the end time of the first interval, it represents the latest end time of the last interval that we decided to keep.
-
Iterating Over Intervals: The code iterates through the rest of the intervals starting from the second interval (since the first interval's end time is stored in
t
).for s, e in intervals[1:]:
Each interval
[s, e]
consists of a start times
and an end timee
. -
Checking for Overlapping: In each iteration, the code checks if the current interval's start time
s
is greater than or equal to the variablet
:-
If
s >= t
, there is no overlap with the last chosen interval, so the current interval can be kept. We then updatet
to the current interval's end timee
. -
If
s < t
, there is an overlap with the last chosen interval, so the current interval needs to be removed, and we incrementans
by 1.
if s >= t: t = e else: ans += 1
-
-
Returning the Result: After the loop finishes,
ans
holds the minimum number of intervals that need to be removed to make all remaining intervals non-overlapping, so it is returned as the final result.return ans
By following the greedy approach, the algorithm ensures that the intervals with the earliest end times are considered first, minimizing potential overlap with future intervals and thus minimizing the number of intervals that need to be removed.
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 illustrate the solution approach with a small example. Suppose we are given the following list of intervals:
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
We want to remove the minimum number of intervals so that no two intervals overlap. Here is how we apply the solution approach:
-
Sorting Intervals: First, we sort the intervals by their end times:
sorted_intervals = [[1, 2], [2, 3], [1, 3], [3, 4]]
-
Initializing Variables: We initialize
ans = 0
andt = 2
, wheret
is the end time of the first interval after sorting. -
Iterating Over Intervals: We iterate through the intervals starting from the second one.
-
Checking for Overlapping:
- Comparing the 2nd interval
[2, 3]
witht
: since2 >= 2
, we updatet
to 3, and no interval is removed. - Comparing the 3rd interval
[1, 3]
witht
: since1 < 3
, this interval overlaps with the previously chosen intervals. We incrementans
to 1. - Comparing the 4th interval
[3, 4]
witht
: since3 >= 3
, we updatet
to 4, and no interval is removed.
- Comparing the 2nd interval
After checking all intervals, the number of intervals to be removed is ans = 1
. This is because the interval [1, 3]
was overlapping, and by removing it, we ensured that no intervals overlap.
The output of our algorithm for this example would be 1
, indicating we need to remove a single interval to eliminate all overlaps.
Solution Implementation
1from typing import List
2
3class Solution:
4 def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
5 # Sort the intervals based on the end time of each interval
6 intervals.sort(key=lambda interval: interval[1])
7
8 # Initialize the count of removed intervals and set the time to compare against
9 removed_intervals_count = 0
10 end_time = intervals[0][1]
11
12 # Iterate through the intervals starting from the second one
13 for start, end in intervals[1:]:
14 # If the current interval does not overlap, update the `end_time`
15 if start >= end_time:
16 end_time = end
17 # If the interval overlaps, increment the count of intervals to remove
18 else:
19 removed_intervals_count += 1
20
21 # Return the total count of removed intervals to avoid overlap
22 return removed_intervals_count
23
1import java.util.Arrays; // Required for Arrays.sort
2import java.util.Comparator; // Required for Comparator
3
4class Solution {
5 public int eraseOverlapIntervals(int[][] intervals) {
6 // Sort the intervals array based on the end time of each interval
7 Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
8
9 // Set 'end' as the end time of the first interval
10 int end = intervals[0][1];
11
12 // Initialize 'overlaps' to count the number of overlapping intervals
13 int overlaps = 0;
14
15 // Iterate through each interval starting from the second one
16 for (int i = 1; i < intervals.length; i++) {
17 // If the current interval does not overlap with the previous, update 'end'
18 if (intervals[i][0] >= end) {
19 end = intervals[i][1];
20 } else {
21 // If the current interval overlaps, increment 'overlaps'
22 overlaps++;
23 }
24 }
25
26 // Return the total number of overlapping intervals to be removed
27 return overlaps;
28 }
29}
30
1#include <vector> // Required for using the vector container
2#include <algorithm> // Required for using the sort algorithm
3
4class Solution {
5public:
6 // Function to find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
7 int eraseOverlapIntervals(vector<vector<int>>& intervals) {
8 // Sort the intervals based on their end time.
9 sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
10 return a[1] < b[1];
11 });
12
13 int nonOverlappingCount = 0; // To keep track of the number of non-overlapping intervals
14 int currentEndTime = intervals[0][1]; // Track the end time of the last added interval
15
16 // Iterate over all intervals starting from the second one
17 for (int i = 1; i < intervals.size(); ++i) {
18 // If the current interval starts after the end of the last added interval, it does not overlap
19 if (currentEndTime <= intervals[i][0]) {
20 currentEndTime = intervals[i][1]; // Update the end time to the current interval's end time
21 } else {
22 // If the current interval overlaps, increment the nonOverlappingCount
23 ++nonOverlappingCount;
24 }
25 }
26
27 // Return the total number of overlapping intervals to remove
28 return nonOverlappingCount;
29 }
30};
31
1function eraseOverlapIntervals(intervals: number[][]): number {
2 // Sort the intervals based on the ending time of each interval
3 intervals.sort((a, b) => a[1] - b[1]);
4
5 // Initialize the end variable to the end of the first interval
6 let lastIntervalEnd = intervals[0][1];
7
8 // Initialize counter for the number of intervals to remove
9 let intervalsToRemove = 0;
10
11 // Iterate through the intervals starting from the second one
12 for (let i = 1; i < intervals.length; i++) {
13 // Current interval being considered
14 let currentInterval = intervals[i];
15
16 // Check if the current interval overlaps with the last non-overlapping interval
17 if (lastIntervalEnd > currentInterval[0]) {
18 // If it overlaps, increment the removal counter
19 intervalsToRemove++;
20 } else {
21 // If it doesn't overlap, update the end to be the end of the current interval
22 lastIntervalEnd = currentInterval[1];
23 }
24 }
25
26 // Return the number of intervals that need to be removed to eliminate all overlaps
27 return intervalsToRemove;
28}
29
Time and Space Complexity
The given Python code aims to find the minimum number of intervals that can be removed from a set of intervals so that none of them overlap. Here's an analysis of its time complexity and space complexity:
Time Complexity
The time complexity of the code is primarily determined by the sorting operation and the single pass through the sorted interval list:
intervals.sort(key=lambda x: x[1])
sorts the intervals based on the end time. Sorting in Python uses the Timsort algorithm, which has a time complexity ofO(n log n)
, wheren
is the number of intervals.- The
for
loop iterates through the list of intervals once. The loop runs inO(n)
as each interval is visited exactly once.
Combining these steps, the overall time complexity is dominated by the sorting step, leading to a total time complexity of O(n log n)
.
Space Complexity
The space complexity of the code is mainly the space required to hold the input and the variables used for the function:
- In-place sorting of the intervals doesn't require additional space proportional to the input size, so the space complexity of the sorting operation is
O(1)
. - The only extra variables that are used include
ans
, andt
. These are constant-size variables and do not scale with the input size.
Hence, the overall space complexity of the code is O(1)
, indicating it requires constant additional space.
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
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
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
Want a Structured Path to Master System Design Too? Donāt Miss This!