Insert Intervals

题目描述

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

解题方法

方法1，利用merge

先插到最后，然后用merge的方法过一遍

方法2，遍历，找到插入位置

Solution

方法1

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

        result = self.merge(intervals)

        return result

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

        def compare(a, b):
            return a.start - b.start

        intervals = sorted(intervals, cmp=compare)
        length = len(intervals)

        result = [intervals[0]]
        for i in range(1, length):
            cur = result[-1]
            if cur.end >= intervals[i].start:
                newInterval = Interval(cur.start, max(cur.end, intervals[i].end)) #should choose the max end
                result[-1] = newInterval
            else:
                result.append(intervals[i])
        return result

方法2

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

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not newInterval:
            return intervals
        if not intervals:
            return [newInterval]
        result = []
        insertPos = 0
        length = len(intervals)
        for i in range(length):
            cur = intervals[i]
            if cur.end < newInterval.start:
                result.append(cur)
                insertPos += 1
            elif cur.start > newInterval.end:
                result.append(cur)
            else:
                newStart = min(cur.start, newInterval.start)
                newEnd = max(cur.end, newInterval.end)
                newInterval.start = newStart
                newInterval.end = newEnd
        result.insert(insertPos, newInterval)
        return result

Reference