56.Merge Intervals

Tags: [queue], [deque], [interval], [merge], [sort]

Com: {fb}, {g}

Link: https://leetcode.com/problems/merge-intervals/#/description

Given a collection of intervals, merge all overlapping intervals.

For example,
Given[1,3],[2,6],[8,10],[15,18],
return[1,6],[8,10],[15,18].

Better Solution: Queue, Sort

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

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if not intervals:
            return []

        intervals.sort(key=lambda x: x.start)
        queue = collections.deque()
        for interval in intervals:
            if not interval:
                continue
            if not queue or not self.can_merge(queue[-1], interval):
                queue.append(interval)
            else:
                queue[-1].end = max(queue[-1].end, interval.end)

        return list(queue)

    def can_merge(self, interval1, interval2):
        return interval1.end >= interval2.start

Solution: Queue, Deque, Sort

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

from collections import deque

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        if not intervals:
            return []

        intervals.sort(key=lambda x: x.start)
        queue = deque()
        for interval in intervals:
            if not queue or not self.can_merge(queue[-1], interval):
                queue.append(interval)
            else:
                last_interval = queue[-1]
                last_interval.end = max(last_interval.end, interval.end)

        result = []
        while queue:
            result.append(queue.popleft())

        return result

    def can_merge(self, interval1, interval2):
        return interval1.end >= interval2.start

Revelation:

• When the two intervals can be merged, we don't need do 'last_interval.start = min(last_interval.start, interval.start)', because we have sorted the intervals based on start ascending, which guarantee the last_interval.start <= interval.start.

Note:

• Time complexity = O(n), n is the number of intervals.