Question: https://oj.leetcode.com/problems/insert-interval/
Question Name: Insert Interval
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | # Definition for an interval. # class Interval: # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution: # @param intervals, a list of Intervals # @param newInterval, a Interval # @return a list of Interval def insert(self, intervals, newInterval): if len(intervals) == 0: return [newInterval] # Empty input # Insert the newInterval according to its start position. # Actually, we could only find out where to insert, and then # divide the following merge code into three parts to avoid insertion. # But the non-insert version would be long code. # # Find the insert position with binary method. begin, end = 0, len(intervals) - 1 while begin <= end: mid = (begin + end) // 2 if newInterval.start > intervals[mid].start: begin = mid + 1 elif newInterval.start < intervals[mid].start: end = mid - 1 else: begin = mid break # Insert the new interval into the old list. intervals = intervals[:begin] + [newInterval] + intervals[begin:] # Do merge if we could previous = Interval(intervals[0].start, intervals[0].end) result = [] for interval in intervals[1:]: if interval.start > previous.end: # Cannot merge the current interval with the previous one result.append(previous) previous = Interval(interval.start, interval.end) else: # Merge the current interval with the previous one, by # extending the end position if possible previous.end = max(interval.end, previous.end) # Record the last one interval result.append(previous) return result |