Lintcode30 Insert Interval solution problem solution

Title Description]

Given a non-overlapping interval list which is sorted by start point.Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Gives a nonoverlapping list of intervals sorted by interval start and end points. Insert a new interval into the list, making sure that the intervals in the list are still ordered and do not overlap (merge intervals if necessary).

[Title Link]

http://www.lintcode.com/en/problem/insert-interval/

[Title Analysis]

Use pos to record where newInterval should be inserted. Iterate the elements in intervals sequentially. If the end of the current interval is smaller than the start of newInterval, add the current interval to the answer, and pos+1; if it is larger than newInterval, add the answer directly; if there is overlap, merge is required. The start of newInterval is the smaller of the two, and the end is the larger of the two. Finally, insert newInterval in pos position.

[Reference answer]

http://www.jiuzhang.com/solutions/insert-interval/