57. Insert Interval

https://leetcode.com/problems/insert-interval/description/?envType=featured-list&envId=top-google-questions?envType=featured-list&envId=top-google-questions

input :

• intervals, newInterval

output :

• 마지막 위치까지의 도달가능 여부를 출력하시오.

조건 :

• 1 <= intervals.length <= 10,000

---

Solution explain : Solution1

idea

• 56. Merge와 매우 비슷하다.
• 길이가 동일하기에 새로운 값을 넣고 정렬을 한 후 다시 overlap 구간을 합친다면 원하는 정답을 얻을 수 있다.

주의

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        intervals.sort()

        ret = [intervals[0]]
        
        def interval(left, right):
            (ll, lr), (rl, rr) = left, right
            if rl <= lr:
                return True
            return False
        
        for i in range(1, len(intervals)):
            prev_ll, prev_lr = ret[-1]
            now_rl, now_rr = intervals[i]
            if interval(ret[-1], intervals[i]):
                ret.pop()
                ret.append([min(prev_ll, now_rl), max(prev_lr, now_rr)])
            else:
                ret.append([now_rl, now_rr])
        return ret