Hợp nhất các khoảng trong Python

Giả sử chúng ta có một tập hợp các khoảng, cần hợp nhất tất cả các khoảng chồng chéo. Ví dụ, nếu các khoảng là [[1,3], [2,6], [8,10], [15,18]], sau khi hợp nhất sẽ là [[1,6],[8,10],[15,18]]. Điều này do hai khoảng [1,3] và [2,6] chồng chéo, được hợp nhất thành [1,6].

Các bước thực hiện

• Nếu danh sách khoảng rỗng, trả về danh sách rỗng.
• Sắp xếp danh sách khoảng bằng thuật toán quicksort.
• stack := ngăn xếp rỗng, đưa intervals[0] vào ngăn xếp.
• Với i từ 1 đến độ dài intervals - 1:
  • last_element := phần tử đỉnh ngăn xếp.
  • Nếu cuối của last_element >= đầu của intervals[i]:
    • Cập nhật cuối của last_element = max(cuối của intervals[i], cuối của last_element).
    • Lấy phần tử ra khỏi ngăn xếp.
    • Đưa last_element trở lại ngăn xếp.
  • Ngược lại đưa intervals[i] vào ngăn xếp.
• Trả về ngăn xếp.

Ví dụ minh họa

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

Đầu vào

[[1,3],[2,6],[8,10],[15,18]]

Đầu ra

[[1, 6], [8, 10], [15, 18]]