[Leet Code] 56. Merge Intervals

[Level] Medium
[Topics] Array Sorting

 

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

https://leetcode.com/problems/merge-intervals/

Idea

Code

class Solution:
    def selection_sort(self, intervals):
        for i in range(len(intervals)):
            smallest = i
            for j in range(i+1, len(intervals)):
                if intervals[j][0] < intervals[smallest][0]:
                    smallest = j
            intervals[smallest],intervals[i] = intervals[i], intervals[smallest]
        return intervals

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = self.selection_sort(intervals)
        merge = [intervals[0]]
        
        for i in range(1, len(intervals)):
            if merge[-1][1] >= intervals[i][0]:
                merge[-1][1] = max(merge[-1][1], intervals[i][1])
            else:
                merge.append(intervals[i])

        return merge