leetcode: 57. Insert Interval

# 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].
#
# Example 2:
# Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
#
# This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

class Interval():
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution():
    def insert(self, xs, new):
        if xs or new:    # 如果 xs 为空，new 为非空，则也可继续进行
            xs.append(new)
            xs.sort(key=lambda x:x.start)
            i = 1
            while i < len(xs):    # len(xs) 每次会自动减一
                if xs[i].start <= xs[i-1].end:
                    xs[i-1].end = max(xs[i-1].end, xs[i].end)
                    del xs[i]
                else:
                    i += 1
        return xs


if __name__ == "__main__":
    print(Solution().insert([Interval(1, 2), Interval(3, 5), Interval(6, 7), Interval(8, 10), Interval(12, 16)], Interval(4, 9)))