Remove Interval from Disjoint Intervals
Given a sorted list of disjoint intervals representing a set of real numbers and an interval toBeRemoved to remove. The task is to remove toBeRemoved interval from the set and return the remaining intervals as a sorted list.
Example:
Input: intervals = {{0,2},{3,4},{5,7}}, toBeRemoved = {1,6}
Output: {{0,1},{6,7}}Input: intervals = {{0,5}}, toBeRemoved = {2,3}
Output: {{0,2},{3,5}}Input: intervals = {{-5,-4},{-3,-2},{1,2},{3,5},{8,9}}, toBeRemoved = {-1,4}
Output: {{-5,-4},{-3,-2},{4,5},{8,9}}
Approach:
Iterate over each interval in the set and check its relation with the interval to be removed. There are three possible cases:
- The current interval is completely outside the interval to be removed. In this case, we simply add the current interval to the result set as it is.
- The current interval is completely inside the interval to be removed. In this case, we skip the current interval as it is to be removed.
- The current interval partially overlaps with the interval to be removed. In this case, we split the current interval into two parts that are outside the interval to be removed and add them to the result set.
Steps-by-step approach:
- Iterates over each interval in the set of intervals.
- For each interval, checks if the current interval is completely outside the interval to be removed. If so, it adds the current interval to the resultSet.
- If the current interval is not completely outside the interval to be removed, further checks if the current interval is completely inside the interval to be removed. If it is, the current interval is skipped.
- If the current interval partially overlaps with the interval to be removed
- splits the current interval into two parts (left and right) based on the removal interval and adds them to the resultSet.
- After processing all intervals, returns the resulting set resultSet.
Below are the implementation of the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to remove an interval from a set of intervals
vector<vector<int> >
removeIntervalFromSet(vector<vector<int> >& intervals,
vector<int>& toBeRemoved)
{
// Size of the intervals set
int setSize = intervals.size();
// Resultant set after removing the interval
vector<vector<int> > resultSet;
// Iterate over each interval in the set
for (auto currInterval : intervals) {
// If current interval is completely outside the
// interval to be removed
if (currInterval[0] > toBeRemoved[1]
|| currInterval[1] < toBeRemoved[0]) {
// Add the current interval to the result set as
// it is
resultSet.push_back(currInterval);
}
else {
// If current interval is completely inside the
// interval to be removed
if (currInterval[0] >= toBeRemoved[0]
&& currInterval[1] <= toBeRemoved[1]) {
// Skip the current interval as it is to be
// removed
continue;
}
// If left part of the current interval is
// outside the interval to be removed
if (currInterval[0] < toBeRemoved[0]) {
// Add the left part to the result set
resultSet.push_back(
{ currInterval[0], toBeRemoved[0] });
}
// If right part of the current interval is
// outside the interval to be removed
if (currInterval[1] > toBeRemoved[1]) {
// Add the right part to the result set
resultSet.push_back(
{ toBeRemoved[1], currInterval[1] });
}
}
}
// Return the resultant set
return resultSet;
}
// Driver code
int main()
{
vector<vector<int> > intervals
= { { 0, 2 }, { 3, 4 }, { 5, 7 } };
vector<int> toBeRemoved = { 1, 6 };
vector<vector<int> > resultSet
= removeIntervalFromSet(intervals, toBeRemoved);
// Print the resultant set
for (auto interval : resultSet) {
cout << "[" << interval[0] << ", " << interval[1]
<< "]" << endl;
}
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// Function to remove an interval from a set of intervals
public static List<List<Integer>> removeIntervalFromSet(List<List<Integer>> intervals, List<Integer> toBeRemoved) {
// Resultant set after removing the interval
List<List<Integer>> resultSet = new ArrayList<>();
// Iterate over each interval in the set
for (List<Integer> currInterval : intervals) {
// If current interval is completely outside the
// interval to be removed
if (currInterval.get(0) > toBeRemoved.get(1) || currInterval.get(1) < toBeRemoved.get(0)) {
// Add the current interval to the result set as it is
resultSet.add(currInterval);
} else {
// If current interval is completely inside the
// interval to be removed
if (currInterval.get(0) >= toBeRemoved.get(0) && currInterval.get(1) <= toBeRemoved.get(1)) {
// Skip the current interval as it is to be removed
continue;
}
// If left part of the current interval is
// outside the interval to be removed
if (currInterval.get(0) < toBeRemoved.get(0)) {
// Add the left part to the result set
resultSet.add(List.of(currInterval.get(0), toBeRemoved.get(0)));
}
// If right part of the current interval is
// outside the interval to be removed
if (currInterval.get(1) > toBeRemoved.get(1)) {
// Add the right part to the result set
resultSet.add(List.of(toBeRemoved.get(1), currInterval.get(1)));
}
}
}
// Return the resultant set
return resultSet;
}
// Driver code
public static void main(String[] args) {
List<List<Integer>> intervals = List.of(List.of(0, 2), List.of(3, 4), List.of(5, 7));
List<Integer> toBeRemoved = List.of(1, 6);
List<List<Integer>> resultSet = removeIntervalFromSet(intervals, toBeRemoved);
// Print the resultant set
for (List<Integer> interval : resultSet) {
System.out.println("[" + interval.get(0) + ", " + interval.get(1) + "]");
}
}
}
# Function to remove an interval from a set of intervals
def remove_interval_from_set(intervals, to_be_removed):
# Resultant set after removing the interval
result_set = []
# Iterate over each interval in the set
for curr_interval in intervals:
# If current interval is completely outside the interval to be removed
if curr_interval[0] > to_be_removed[1] or curr_interval[1] < to_be_removed[0]:
# Add the current interval to the result set as it is
result_set.append(curr_interval)
else:
# If current interval is completely inside the interval to be removed
if curr_interval[0] >= to_be_removed[0] and curr_interval[1] <= to_be_removed[1]:
# Skip the current interval as it is to be removed
continue
# If left part of the current interval is outside the interval to be removed
if curr_interval[0] < to_be_removed[0]:
# Add the left part to the result set
result_set.append([curr_interval[0], to_be_removed[0]])
# If right part of the current interval is outside the interval to be removed
if curr_interval[1] > to_be_removed[1]:
# Add the right part to the result set
result_set.append([to_be_removed[1], curr_interval[1]])
# Return the resultant set
return result_set
# Driver code
intervals = [[0, 2], [3, 4], [5, 7]]
to_be_removed = [1, 6]
result_set = remove_interval_from_set(intervals, to_be_removed)
# Print the resultant set
for interval in result_set:
print("[%d, %d]" % (interval[0], interval[1]))
// Function to remove an interval from a set of intervals
function removeIntervalFromSet(intervals, toBeRemoved) {
// Resultant set after removing the interval
const resultSet = [];
// Iterate over each interval in the set
for (const currInterval of intervals) {
// If current interval is completely outside the interval to be removed
if (currInterval[0] > toBeRemoved[1] || currInterval[1] < toBeRemoved[0]) {
// Add the current interval to the result set as it is
resultSet.push(currInterval);
} else {
// If current interval is completely inside the interval to be removed
if (currInterval[0] >= toBeRemoved[0] && currInterval[1] <= toBeRemoved[1]) {
// Skip the current interval as it is to be removed
continue;
}
// If left part of the current interval is outside the interval to be removed
if (currInterval[0] < toBeRemoved[0]) {
// Add the left part to the result set
resultSet.push([currInterval[0], toBeRemoved[0]]);
}
// If right part of the current interval is outside the interval to be removed
if (currInterval[1] > toBeRemoved[1]) {
// Add the right part to the result set
resultSet.push([toBeRemoved[1], currInterval[1]]);
}
}
}
// Return the resultant set
return resultSet;
}
// Driver code
const intervals = [[0, 2], [3, 4], [5, 7]];
const toBeRemoved = [1, 6];
const resultSet = removeIntervalFromSet(intervals, toBeRemoved);
// Print the resultant set
for (const interval of resultSet) {
console.log(`[${interval[0]}, ${interval[1]}]`);
}
Output
[0, 1] [6, 7]
Time Complexity: O(n), where n is the number of intervals
Auxiliary Space: O(n)
Contact Us