Fork me on GitHub

Insert Interval

Posted on

Insert Interval

Description

https://leetcode.com/problems/insert-interval/description/

Solution

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
# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
def insert(self, intervals, newInterval):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """
    if len(intervals) == 0:
    return [newInterval]

    insert_start_index = len(intervals)
    for i in range(0, len(intervals)):
    if newInterval.start <= intervals[i].start:
    insert_start_index = i
    break

    insert_end_index = insert_start_index
    while insert_end_index < len(intervals) and newInterval.end >= intervals[insert_end_index].start:
    insert_end_index += 1

    newInterval.end = max(newInterval.end, 0 if insert_end_index < 1 else intervals[insert_end_index - 1].end)

    ##Do not need insertion
    if insert_start_index >= 1 and newInterval.start <= intervals[insert_start_index - 1].end:
    intervals[insert_start_index - 1].end = max(intervals[insert_start_index - 1].end, newInterval.end)
    return intervals[0:insert_start_index] + intervals[insert_end_index:len(intervals)]
    ##Need insert seperately
    else:
    return intervals[0:insert_start_index] + [newInterval] + intervals[insert_end_index:len(intervals)]