[LeetCode] 1272. Remove Interval

1272. Remove Interval

Medium

A set of real numbers can be represented as the union of several disjoint intervals, where each interval is in the form [a, b). A real number x is in the set if one of its intervals [a, b) contains x (i.e. a <= x < b).

You are given a sorted list of disjoint intervals intervals representing a set of real numbers as described above, where intervals[i] = [ai, bi] represents the interval [ai, bi). You are also given another interval toBeRemoved.

Return the set of real numbers with the interval toBeRemoved removed from intervals. In other words, return the set of real numbers such that every x in the set is in intervals but not in toBeRemoved. Your answer should be a sorted list of disjoint intervals as described above.

 

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

Example 3:

Input: intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
Output: [[-5,-4],[-3,-2],[4,5],[8,9]]

 

Constraints:

• 1 <= intervals.length <= 104
• -109 <= ai < bi <= 109

---

문제 풀이

1. 인터벌들이 주어진다. 지워야하는 구간이 주어진다. 
2. 인터벌들 중에 지워야하는 구간내에 포함이 된다면 지워야하는 부분을 잘라 답을 완성해야한다.
3. 제한은 10^4 이기 때문에 N^2 알고리즘을 사용해도 문제가 없어보인다. 
4. 전체 인터벌들을 하나씩 확인한다.
5. 지우는 구간의 조건은 총 세개로 지정할 수 있다. 
6. 이 조건 세가지 말고도, 만약에 지우는 구간 밖에 인터벌이 있는 조건도 처리해줘야한다.

조건

1. 인터벌 사이에 지우는 구간 첫 포인트가 포함될때
   인터벌    [    ]
   지움          [    ]
2. 인터벌 사이에 지우는 구간 마지막 포인트가 포함될때
   인터벌    [    ]
   지움    [    ]
3. 인터벌이 지우는 구간 안에 들어 갈때 
   인터벌    [    ]
   지움     [         ]

소스 코드

class Solution:
    def removeInterval(self, intervals: List[List[int]], toBeRemoved: List[int]) -> List[List[int]]:
        result = []
        for interval in intervals:
            if interval[1] < toBeRemoved[0] or toBeRemoved[1] < interval[0]:
                result.append(interval)
            elif toBeRemoved[0] <= interval[0] and toBeRemoved[1] < interval[1]:
                result.append([toBeRemoved[1], interval[1]])
            elif interval[0] < toBeRemoved[0] and toBeRemoved[1] < interval[1]:
                result.append([interval[0], toBeRemoved[0]])
                result.append([toBeRemoved[1], interval[1]])
            elif interval[0] < toBeRemoved[0] and interval[1] <= toBeRemoved[1]:
                result.append([interval[0], toBeRemoved[0]])
        return result