Remove Interval - Leetcode Solution

Problem Statement:

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6] Output: [[0,1],[6,7]] Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3] Output: [[0,2],[3,5]]

Approach:

The main idea is to check each interval of the input if it does not overlap with the toBeRemoved interval. If it overlaps then we split the input interval into two and evaluate again.

Let's say given intervals is [a,b] and toBeRemoved interval is [c,d]. If the intervals don’t overlap [a>d or b<=c], then we add it to the result. If the interval is fully overlapped [a<c,b>d], then we add nothing. If only the left part of the interval overlaps [c<=a<=d<b], we add [d,b] to the result. If only the right part of the interval overlaps [a<=c<b<=d], then we add [a,c] to the result.

Algorithm:

1. Initialize an empty list res
2. Traverse through the intervals: a. If the interval overlaps completely with the toBeRemoved interval, then do nothing and move to the next interval. b. If the interval does not overlap with the toBeRemoved interval, then add it to the result(res) list and move to the next interval. c. If the interval overlaps partially with the toBeRemoved interval, then split the interval and add the valid parts to the result(res) list.
3. Return the result(res) list as the output.

Code:

Time complexity:

The time complexity of the above algorithm is O(n) where n is the number of intervals in the input list. This is because the algorithm traverses through each interval only once.

1