input :
- intervals
output :
- 마지막 위치까지의 도달가능 여부를 출력하시오.
조건 :
- 1 <= intervals.length <= 10,000
Solution explain : Solution1
idea
- 주된 점은 정렬을 우선 해서 두 원소 중 [0], [1] 중 [0]에 집중을 해야 한다는 것이다.
- 우선적으로 left[1], right[0]를 비교하여 해당 구간이 overlap되는지 확인한다.
- 해당 값들을 확인한 후에 오버랩 된다면 원래 저장되어 있던 값을 빼서 업데이트한다.
주의
- [1, 4], [2, 3]과 같은 경우 left 파라미터가 모두를 만족시키기 때문에 해당값을 가져 가야 한다.
- 그렇기에 범위를 min, max 연산을 통해 확인한다.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
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