menu

[LeetCode] 056. Merge Intervals

Problem (Medium)

056. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

  • Input: [[1,3],[2,6],[8,10],[15,18]]
  • Output: [[1,6],[8,10],[15,18]]
  • Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

  • Input: [[1,4],[4,5]]
  • Output: [[1,5]]
  • Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Approach 1: (My Solution)

Idea

  • First, sorted the intervals with insterval’s start value;
  • Second, put the sorted intervals in a single list: [start_1, end_1, start_2, end_2, …, start_n, end_n];
  • Third, loop this list, when end_i > start_i+1, then, pop these two values (but need to save end_i to a tmp variable). Then, end_i+1 = end_i if end_i > end_i+1, else remain original end_i+1;
  • Finally, pick each pair in the processed list as the result interval instance and add to the final result list.

Solution

# Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution1:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        sorted_int = sorted(intervals, key=lambda x:x.start)
        l = []
        for i in sorted_int:
            l.append(i.start)
            l.append(i.end)
        i= 1
        while i + 2 < len(l):
            if l[i] >= l[i+1]:
                tmp = l[i]
                l.pop(i)
                l.pop(i)
                if tmp > l[i]:
                    l[i] = tmp
            else:
                i += 2
        res = []
        for i in range(0, len(l), 2):
            res.append(Interval(l[i], l[i+1]))
        return res

Complexity

  • Time: $O(n\log n)$
  • Space: $O()$



KF

Comments