Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1272.html

1272. Remove Interval

Level

Medium

Description

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]]

Constraints:

  • 1 <= intervals.length <= 10^4
  • -10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

Solution

For each interval in intervals, compare the interval with the interval toBeRemoved, and store the remove status for each interval.

There are 5 statuses, each of which should be dealt with in the following way.

Status 0: interval[1] <= toBeRemoved[0] || interval[0] >= toBeRemoved[1]. This status means that interval is disjoint with toBeRemoved, so simply keep interval`.

Status 1: interval[0] >= toBeRemoved[0] && interval[1] <= toBeRemoved[1]. This status means that interval is completely contained in toBeRemoved, so interval is removed.

Status 2: interval[0] < toBeRemoved[0] && interval[1] > toBeRemoved[1]. This status means that toBeRemoved is completely contained in interval. After toBeRemoved is removed, there will be two disjoint intervals, which are [interval[0], toBeRemoved[0]] and [toBeRemoved[1], interval[1]].

Status 3: interval[0] < toBeRemoved[0] && interval[1] > toBeRemoved[0] && interval[1] <= toBeRemoved[1]. After toBeRemoved is removed, only the left part of interval will be kept, and the remaining interval is [interval[0], toBeRemoved[0]].

Status 4: interval[0] >= toBeRemoved[0] && interval[0] < toBeRemoved[1] && interval[1] > toBeRemoved[1]. After toBeRemoved is removed, only the right part of interval will be kept, and the remaining interval is [toBeRemoved[1], interval[1]].

Do the corresponding operations for each interval in intervals.

Solution-2

This is also a problem that belongs to the scan line. The idea is also relatively straightforward, traverse the input array, and the sub-intervals that do not overlap the interval toBeRemoved that need to be removed are directly added to the result set.

If there is an overlap with toBeRemoved, compare the left and right boundaries of the two to find out what interval needs to be removed.

  • 
    public class Remove_Interval {
    
        public static void main(String[] args) {
            Remove_Interval out = new Remove_Interval();
            Solution s = out.new Solution();
    
            System.out.println(s.removeInterval(new int[][]{ {0,2}, {3,4}, {5,7} }, new int[]{1,6})); // [[0,1],[6,7]]
        }
    
        // to clarify: overlap in between intervals ? if so then more complexed
        class Solution {
            public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
    
                List<List<Integer>> res = new ArrayList<>();
    
                if (intervals == null || intervals.length == 0) {
                    return res;
                }
    
                for (int[] i : intervals) {
                    // no overlap
                    if (i[1] <= toBeRemoved[0] || i[0] >= toBeRemoved[1]) {
                        res.add(Arrays.asList(i[0], i[1]));
                    }
                    // i[1] > toBeRemoved[0] && i[0] < toBeRemoved[1]
                    else {
                        // left end no overlap
                        if (i[0] < toBeRemoved[0]) {
                            res.add(Arrays.asList(i[0], toBeRemoved[0]));
                        }
                        // right end no overlap
                        if (i[1] > toBeRemoved[1]) {
                            res.add(Arrays.asList(toBeRemoved[1], i[1]));
                        }
    
                        // i inside of toBeRemoved, then remove. ie no add to result list
                    }
                }
                return res;
            }
        }
    }
    
    class Solution {
        public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
            int x = toBeRemoved[0], y = toBeRemoved[1];
            List<List<Integer>> ans = new ArrayList<>();
            for (var e : intervals) {
                int a = e[0], b = e[1];
                if (a >= y || b <= x) {
                    ans.add(Arrays.asList(a, b));
                } else {
                    if (a < x) {
                        ans.add(Arrays.asList(a, x));
                    }
                    if (b > y) {
                        ans.add(Arrays.asList(y, b));
                    }
                }
            }
            return ans;
        }
    }
    
    
  • class Solution {
    public:
        vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
            int x = toBeRemoved[0], y = toBeRemoved[1];
            vector<vector<int>> ans;
            for (auto& e : intervals) {
                int a = e[0], b = e[1];
                if (a >= y || b <= x) {
                    ans.push_back(e);
                } else {
                    if (a < x) {
                        ans.push_back({a, x});
                    }
                    if (b > y) {
                        ans.push_back({y, b});
                    }
                }
            }
            return ans;
        }
    };
    
  • '''
    >>> a
    [1, 2, 3, 4, 5]
    >>>
    >>> x, y = a
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    ValueError: too many values to unpack
    >>> x,y,z,p,q = a
    >>> x
    1
    >>> y
    2
    >>> z
    3
    '''
    class Solution:
        def removeInterval(
            self, intervals: List[List[int]], toBeRemoved: List[int]
        ) -> List[List[int]]:
            x, y = toBeRemoved
            ans = []
            for a, b in intervals:
                if a >= y or b <= x:
                    ans.append([a, b])
                else:
                    if a < x:
                        ans.append([a, x]) # in this else block, meaning b>x, so no need to append [a,min(b,x)]
                    if b > y:
                        ans.append([y, b])
                    # if x < a < b < y, then skip (a,b), do nothing
            return ans
    
    ############
    
    class Solution:
        def removeInterval(
            self, intervals: List[List[int]], toBeRemoved: List[int]
        ) -> List[List[int]]:
            result = []
    
            for ind, intv in enumerate(intervals):
                if intv[1] < toBeRemoved[0] or toBeRemoved[1] < intv[0]:
                    result.append(intv)
                else:
                    if intv[0] < toBeRemoved[0]:
                        result.append([intv[0], min(intv[1], toBeRemoved[0])]) # min() is not needed
                    if intv[1] > toBeRemoved[1]:
                        result.append([max(intv[0], toBeRemoved[1]), intv[1]])
    
            return result
    
  • func removeInterval(intervals [][]int, toBeRemoved []int) (ans [][]int) {
    	x, y := toBeRemoved[0], toBeRemoved[1]
    	for _, e := range intervals {
    		a, b := e[0], e[1]
    		if a >= y || b <= x {
    			ans = append(ans, e)
    		} else {
    			if a < x {
    				ans = append(ans, []int{a, x})
    			}
    			if b > y {
    				ans = append(ans, []int{y, b})
    			}
    		}
    	}
    	return
    }
    

All Problems

All Solutions