Insert Interval · 數據結構與算法/leetcode/lintcode題解

# Insert Interval ### Source - leetcode: [Insert Interval | LeetCode OJ](https://leetcode.com/problems/insert-interval/) - lintcode: [(30) Insert Interval](http://www.lintcode.com/en/problem/insert-interval/) ~~~ 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). Example Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]]. Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]]. ~~~ ### 題解這道題看似簡單，但其實實現起來不那么容易，因為若按照常規思路，需要分很多種情況考慮，如半邊相等的情況。以返回新數組為例，首先，遍歷原數組肯定是必須的，以`[N]`代表`newInterval`, `[I]`代表當前遍歷到的`interval`, 那么有以下幾種情況： 1. `[N], [I]` <==> `newInterval.end < interval.start`, 由于 intervals 中的間隔數組已經為升序排列，那么遍歷到的下一個間隔的左邊元素必然也大于新間隔的右邊元素。 1. `[NI]` <==> `newInterval.end == interval.start`，這種情況下需要進行合并操作。 1. `[IN]` <==> `newInterval.start == interval.end`, 這種情況下也需要進行合并。 1. `[I], [N]` <==> `newInterval.start > interval.end`, 這意味著`newInterval`有可能在此處插入，也有可能在其后面的間隔插入。故遍歷時需要在這種情況下做一些標記以確定最終插入位置。由于間隔都是互不重疊的，故其關系只可能為以上四種中的某幾個。1和4兩種情況很好處理，關鍵在于2和3的處理。由于2和3這種情況都將生成新的間隔，且這種情況一旦發生，**原來的`newInterval`即被新的合并間隔取代，這是一個非常關鍵的突破口。** ### Java ~~~ /** * Definition of Interval: * public classs Interval { * int start, end; * Interval(int start, int end) { * this.start = start; * this.end = end; * } */ class Solution { /** * Insert newInterval into intervals. * @param intervals: Sorted interval list. * @param newInterval: A new interval. * @return: A new sorted interval list. */ public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) { ArrayList<Interval> result = new ArrayList<Interval>(); if (intervals == null || intervals.isEmpty()) { if (newInterval != null) { result.add(newInterval); } return result; } int insertPos = 0; for (Interval interval : intervals) { if (newInterval.end < interval.start) { // case 1: [new], [old] result.add(interval); } else if (interval.end < newInterval.start) { // case 2: [old], [new] result.add(interval); insertPos++; } else { // case 3, 4: [old, new] or [new, old] newInterval.start = Math.min(newInterval.start, interval.start); newInterval.end = Math.max(newInterval.end, interval.end); } } result.add(insertPos, newInterval); return result; } } ~~~ ### 源碼分析源碼的精華在case 3 和 case 4的處理，case 2用于確定最終新間隔的插入位置。之所以不在 case 1立即返回，有兩點考慮：一是代碼的復雜性(需要用到 addAll 添加數組部分元素)；二是case2, case3, case 4有可能正好遍歷到數組的最后一個元素，如果在 case 1就返回的話還需要單獨做一判斷。 ### 復雜度分析遍歷一次，時間復雜度 O(n)O(n)O(n). 不考慮作為結果返回占用的空間 result, 空間復雜度 O(1)O(1)O(1). ### Reference - [Insert Interval 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/insert-interval/)