สมมติว่าเรามีชุดของช่วง (intervals) เราต้องรวมช่วงที่ทับซ้อนกันทั้งหมด ตัวอย่างเช่น ถ้าช่วงคือ [[1,3], [2,6], [8,10], [15,18]] หลังจากรวมแล้วจะได้ [[1,6], [8,10], [15,18]] เนื่องจากช่วง [1,3] และ [2,6] ทับซ้อนกัน จึงรวมเป็น [1,6]
ขั้นตอนการทำงาน
- ถ้ารายการช่วงว่าง ให้คืนค่ารายการว่าง
- จัดเรียงรายการช่วงโดยใช้ quicksort
- สร้างสแต็กว่าง ใส่
intervals[0]ลงไป - วนลูป
iจาก 1 ถึง ความยาวของ intervals - 1:last_element := top element of stack- ถ้า
end of last_element >= first element of intervals[i]:end of last_element = max(end of intervals[i], end of last_element)- นำ
last_elementออกจากสแต็ก แล้วใส่กลับเข้าไป
- มิฉะนั้น ใส่
intervals[i]ลงในสแต็ก
- คืนค่าสแต็ก
ตัวอย่างโค้ด
class Solution(object):
def merge(self, intervals):
if len(intervals) == 0:
return []
self.quicksort(intervals, 0, len(intervals)-1)
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]]
