leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

merge-intervalsV1.py (837B)

      1 # idea:
      2 
      3 # sort
      4 # go from left to right, merging when applicable in new array
      5 
      6 # TC: O(nlogn)
      7 
      8 
      9 class Solution:
     10     def merge(self, intervals: List[List[int]]) -> List[List[int]]:
     11 
     12         intervals.sort()
     13         merged = []
     14 
     15         for i in range(0, len(intervals)):
     16 
     17             current = intervals[i]
     18             if len(intervals) - 1 != i and overlapping(intervals[i], intervals[i + 1]):
     19                 current = merge(intervals[i], intervals[i + 1])
     20 
     21             if merged and overlapping(merged[-1], current):
     22                 merged[-1] = merge(merged[-1], current)
     23             else:
     24                 merged.append(current)
     25 
     26         return merged
     27 
     28 
     29 # int1[0] <= int2[0]
     30 def overlapping(int1, int2):
     31     if int1[1] >= int2[0]:
     32         return True
     33 
     34 
     35 def merge(int1, int2):
     36     return [min(int1[0], int2[0]), max(int1[1], int2[1])]