1272. Remove Interval
Problem Description
In this problem, we're dealing with a mathematical representation of sets using intervals of real numbers. Each interval is represented as [a, b)
, which means it includes all real numbers x
such that a <= x < b
.
We are provided with two things:
- A sorted list of disjoint intervals,
intervals
, which together make up a set. The intervals are disjoint, meaning they do not overlap, and they are sorted in ascending order based on their starting points. - Another interval,
toBeRemoved
, which we need to remove from the set represented byintervals
.
Our objective is to return a new set of real numbers obtained by removing toBeRemoved
from intervals
. This set also needs to be represented as a sorted list of disjoint intervals. We need to consider that part of an interval might be removed, all of it might be removed, or it might not be affected at all, depending on whether it overlaps with toBeRemoved
.
Intuition
The key to solving this problem is to examine each interval in intervals
and figure out its relation with toBeRemoved
. There are three possibilities:
- The interval is completely outside the range of
toBeRemoved
and therefore remains unaffected. - The interval is partially or completely inside the range of
toBeRemoved
and needs to be trimmed or removed. - The interval straddles the edges of
toBeRemoved
and might need to be split into two intervals.
Given that intervals
is sorted, we can iterate over each interval and handle the cases as follows:
- If the current interval ends before
toBeRemoved
starts or starts aftertoBeRemoved
ends, it's disjoint and can be added to the result as is. - If there is overlap, we may need to trim the current interval. If the start of the current interval is before
toBeRemoved
, we can take the portion from the interval's start up to the start oftoBeRemoved
. Similarly, if the interval ends aftertoBeRemoved
, we can take the portion from the end oftoBeRemoved
to the interval's end. - We need to handle the edge cases where
toBeRemoved
completely covers an interval, in which case we add nothing to the result for that interval.
By iterating through each interval once, and considering these cases, we can construct our output set of intervals with toBeRemoved
taken out.
Solution Approach
The provided solution employs a straightforward approach to tackle the problem by iterating through each interval in the given sorted list intervals
and comparing it with the toBeRemoved
interval. Here's a step by step process used in the implementation:
-
The solution starts by initializing an empty list
ans
, which will eventually contain the resulting set of intervals after the removal process. -
It then enters a loop over each interval
[a, b]
in theintervals
list. -
For each interval, it checks whether there is an intersection with the
toBeRemoved
interval,[x, y]
. It does this by verifying two conditions:- If
a >= y
, then the interval[a, b]
is completely aftertoBeRemoved
and thus is unaffected. - If
b <= x
, then the interval[a, b]
is completely beforetoBeRemoved
and also remains unaffected.
- If
-
When either of the above conditions is true, the current interval can be added directly to the
ans
list without modification since it doesn't intersect withtoBeRemoved
. -
If the interval does intersect with
toBeRemoved
, the solution needs to handle slicing the interval into potentially two parts:- If the start of the interval
a
is beforex
(the start oftoBeRemoved
), then the segment[a, x)
of the original interval is unaffected by the removal and is added toans
. - Similarly, if the end of the interval
b
is aftery
(the end oftoBeRemoved
), then the segment[y, b)
remains after the removal and is also added toans
.
- If the start of the interval
-
The loops continue for all intervals in
intervals
, applying the above logic. -
After processing all intervals, the solution returns the
ans
list, which now contains the modified set of intervals, representing the original set with thetoBeRemoved
interval excluded.
The algorithm makes use of simple conditional checks and relies on the sorted nature of the input intervals for its correctness and efficiency. The overall time complexity is O(n)
, where n
is the number of intervals in intervals
, since it processes each interval exactly once.
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 consider the following small example to illustrate the solution approach. Assume we have the following intervals
list and toBeRemoved
interval:
intervals = [[1, 4), [6, 8), [10, 13)]
toBeRemoved = [7, 12)
Using the steps outlined in the solution approach:
Step 1: Initialize Result List
ans = []
(empty to begin with)
Step 2: Loop Over Each Interval in intervals
- Current interval
[1, 4)
.
Step 3: Check for Intersection with toBeRemoved
- The interval
[1, 4)
does not intersect with[7, 12)
, as4 < 7
. - Since the interval is completely before
toBeRemoved
, add it toans
:ans = [[1, 4)]
.
Next, we take the interval [6, 8)
.
Step 3: Check for Intersection with toBeRemoved
- The interval
[6, 8)
does intersect with[7, 12)
since the interval starts before and ends in the range oftoBeRemoved
.
Step 5: Handle Slicing the Interval
- The start of the interval
6
is before the start oftoBeRemoved
7
. - Add the segment
[6, 7)
toans
:ans = [[1, 4), [6, 7)]
.
Next, we take the interval [10, 13)
.
Step 3: Check for Intersection with toBeRemoved
- The interval
[10, 13)
does intersect with[7, 12)
, because the interval starts inside and ends after the range oftoBeRemoved
.
Step 5: Handle Slicing the Interval
- Since the end of the interval
13
is after the end oftoBeRemoved
12
, we add the segment[12, 13)
toans
:ans = [[1, 4), [6, 7), [12, 13)]
.
Step 6: Continue the Loop
- No more intervals to process.
Step 7: Return the ans
List
- The final result is
ans = [[1, 4), [6, 7), [12, 13)]
.
The solution approach has efficiently handled the example intervals
list by considering the toBeRemoved
interval and has produced a result that correctly represents the set after removal.
Solution Implementation
1from typing import List
2
3class Solution:
4 def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
5 # Extracting start and end points of the interval to be removed
6 removal_start, removal_end = toBeRemoved
7
8 # This will store the final list of intervals after removing the specified interval
9 updated_intervals = []
10
11 # Iterate through each interval in the provided list of intervals
12 for interval_start, interval_end in intervals:
13 # If the current interval doesn't overlap with the interval to be removed,
14 # we can add it to the updated list as-is
15 if interval_start >= removal_end or interval_end <= removal_start:
16 updated_intervals.append([interval_start, interval_end])
17 else:
18 # If there is an overlap and the start of the current interval
19 # is before the start of the interval to be removed,
20 # add the non-overlapping part to the result.
21 if interval_start < removal_start:
22 updated_intervals.append([interval_start, removal_start])
23
24 # Similarly, if the end of the current interval is after the end of
25 # the interval to be removed, add the non-overlapping part to the result.
26 if interval_end > removal_end:
27 updated_intervals.append([removal_end, interval_end])
28
29 # Return the updated list of intervals after removal
30 return updated_intervals
31
1class Solution {
2
3 // Function to remove a specific interval from a list of intervals
4 public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
5 // x and y represents the start and end of the interval to be removed
6 int removeStart = toBeRemoved[0];
7 int removeEnd = toBeRemoved[1];
8
9 // Preparing a list to store the resulting intervals after removal
10 List<List<Integer>> updatedIntervals = new ArrayList<>();
11
12 // Iterate through each interval in the input intervals array
13 for (int[] interval : intervals) {
14 // a and b represents the start and end of the current interval
15 int start = interval[0];
16 int end = interval[1];
17
18 // Check if the current interval is completely before or after the interval to be removed
19 if (start >= removeEnd || end <= removeStart) {
20 // Add to the result as there is no overlap
21 updatedIntervals.add(Arrays.asList(start, end));
22 } else {
23 // If there's an overlap, we may need to add the non-overlapping parts of the interval
24 if (start < removeStart) {
25 // Add the part of the interval before the interval to be removed
26 updatedIntervals.add(Arrays.asList(start, removeStart));
27 }
28 if (end > removeEnd) {
29 // Add the part of the interval after the interval to be removed
30 updatedIntervals.add(Arrays.asList(removeEnd, end));
31 }
32 }
33 }
34
35 // Return the list of updated intervals
36 return updatedIntervals;
37 }
38}
39
1class Solution {
2public:
3 // Function to remove the interval `toBeRemoved` from the list of `intervals`
4 vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
5 // toBeRemoved[0] is the start of the interval to be removed, toBeRemoved[1] is the end
6 int removeStart = toBeRemoved[0], removeEnd = toBeRemoved[1];
7 vector<vector<int>> updatedIntervals; // This will store the final intervals after removal
8
9 // Iterate through all intervals
10 for (auto& interval : intervals) {
11 int start = interval[0], end = interval[1]; // Start and end of the current interval
12
13 // Check if the current interval is completely outside the toBeRemoved interval
14 if (start >= removeEnd || end <= removeStart) {
15 // Add interval to the result as it doesn't overlap with toBeRemoved
16 updatedIntervals.push_back(interval);
17 } else {
18 // Check if part of the interval is before toBeRemoved
19 if (start < removeStart) {
20 // Add the part of interval before toBeRemoved
21 updatedIntervals.push_back({start, removeStart});
22 }
23 // Check if part of the interval is after toBeRemoved
24 if (end > removeEnd) {
25 // Add the part of interval after toBeRemoved
26 updatedIntervals.push_back({removeEnd, end});
27 }
28 }
29 }
30 // Return the final list of intervals after removal
31 return updatedIntervals;
32 }
33};
34
1// Define the interval type as a tuple of two numbers
2type Interval = [number, number];
3
4// Function to remove the interval `toBeRemoved` from the list of `intervals`
5function removeInterval(intervals: Interval[], toBeRemoved: Interval): Interval[] {
6 // `toBeRemoved[0]` is the start of the interval to be removed, `toBeRemoved[1]` is the end
7 const removeStart = toBeRemoved[0];
8 const removeEnd = toBeRemoved[1];
9
10 // This will store the final intervals after removal
11 const updatedIntervals: Interval[] = [];
12
13 // Iterate through all intervals
14 for (const interval of intervals) {
15 // `start` and `end` of the current interval
16 const start = interval[0];
17 const end = interval[1];
18
19 // Check if the current interval is completely outside the toBeRemoved interval
20 if (start >= removeEnd || end <= removeStart) {
21 // Add the interval to the result as it doesn't overlap with toBeRemoved
22 updatedIntervals.push(interval);
23 } else {
24 // Check if part of the interval is before toBeRemoved
25 if (start < removeStart) {
26 // Add the part of the interval before toBeRemoved
27 updatedIntervals.push([start, removeStart]);
28 }
29 // Check if part of the interval is after toBeRemoved
30 if (end > removeEnd) {
31 // Add the part of the interval after toBeRemoved
32 updatedIntervals.push([removeEnd, end]);
33 }
34 }
35 }
36
37 // Return the final list of intervals after removal
38 return updatedIntervals;
39}
40
Time and Space Complexity
The code snippet provided is for a function that removes an interval from a list of existing intervals and returns the resulting list of disjoint intervals after the removal. The computational complexity analysis for time and space complexity is as follows:
Time complexity:
The primary operation in this function occurs within a single loop that iterates over all the original intervals in the list intervals
. Within each iteration of the loop, the function performs constant-time checks and operations to possibly add up to two intervals to the ans
list. Since there are no nested loops and the operations inside the loop are of constant time complexity, the overall time complexity of the function is directly proportional to the number of intervals n
in the input list. Therefore, the time complexity is O(n)
.
Space complexity:
For space complexity, the function creates a new list ans
to store the resulting intervals after the potential removal and modification of the existing intervals. In the worst-case scenario, where no interval is completely removed and every interval needs to be split into two parts (one occurring before x
and one after y
of the toBeRemoved
interval), the resulting list could potentially hold up to 2n
intervals - doubling the input size. However, notice that this is a linear relationship with respect to the number of input intervals n
. Therefore, the space complexity of the function is O(n)
as well.
In summary, both the time complexity and space complexity of the given code are O(n)
, where n
is the number of intervals in the input list intervals
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
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
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time