Python Solution: Greedy Algorithm


  • 0
    B
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        '''
        not sorted, but if we sort then we can do a greedy algorithm
        '''
        #sort array
        sorted_intervals = sorted(intervals, key=lambda x:x.start)
        result = []
        for i in range(len(sorted_intervals)):
            curr_interval = sorted_intervals[i]
            
            if result and result[-1].end >= curr_interval.start:
                prev = result[-1]
                #there's an overlap, merge
                result[-1].end = max(prev.end, curr_interval.end)
            else:
                result += [curr_interval]
        
        return result

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.