구간 모음이 있다고 가정하고 겹치는 구간을 모두 병합해야 합니다. 따라서 간격이 [[1,3], [2,6], [8,10], [15,18]]과 같으면 병합 후 간격은 [[1,6],[8,10 ],[15,18]]. 겹치는 두 개의 간격이 있기 때문입니다. 간격은 [1,3]과 [2,6]이며 이들은 [1,6]으로 병합됩니다.
단계를 살펴보겠습니다 -
- 간격 목록 길이가 0이면 빈 목록을 반환합니다.
- 빠른 정렬 메커니즘을 사용하여 간격 목록 정렬
- stack :=빈 스택, 스택에 간격[0] 삽입
- i의 경우 범위 1에서 간격 길이 – 1
- last_element :=스택의 최상위 요소
- last_element의 끝>=간격[i]의 첫 번째 요소인 경우
- last_element의 끝 =간격의 끝[i]의 최대값 및 last_element의 끝
- 스택에서 요소 팝
- last_element를 스택에 푸시
- 기타 푸시 간격[i]을 스택으로
- 반환 스택
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ if len(intervals) == 0: return [] self.quicksort(intervals,0,len(intervals)-1) #for i in intervals: #print(i.start, i.end) stack = [] stack.append(intervals[0]) for i in range(1,len(intervals)): last_element= stack[len(stack)-1] if last_element[1] >= intervals[i][0]: last_element[1] = max(intervals[i][1],last_element[1]) stack.pop(len(stack)-1) stack.append(last_element) else: stack.append(intervals[i]) return stack def partition(self,array,start,end): pivot_index = start for i in range(start,end): if array[i][0]<=array[end][0]: array[i],array[pivot_index] =array[pivot_index],array[i] pivot_index+=1 array[end],array[pivot_index] =array[pivot_index],array[end] return pivot_index def quicksort(self,array,start,end): if start<end: partition_index = self.partition(array,start,end) self.quicksort(array,start,partition_index-1) self.quicksort(array, partition_index + 1, end) ob1 = Solution() print(ob1.merge([[1,3],[2,6],[8,10],[15,18]]))
입력
[[1,3],[2,6],[8,10],[15,18]]
출력
[[1, 6], [8, 10], [15, 18]]