2017年1月5日 星期四

LeetCode#57 Insert Interval

分析


首先，我們把題目給的兩個輸入樣本在方格紙上畫出來：

從上圖馬上產生一個直覺，就是首先應該把 newInterval 插入正確的位址，題目已經告訴你這些區間是排序過的(You may assume that the intervals were initially sorted according to their start times.)，所以可以放心使用 binary search 插入。

第二步合併就不太容易，但仔細觀察後，發現有兩種重疊(overlapped)的情形：

情形 1


從上圖可以看出 x1 < x3 < x2 此時可以確定區間 [x1,x2] 與 [x3,x4] 重疊，從圖中可以看出起點為 x1，終點為 x6，也就合併的方法是先取區間#i-1  [start#i-1, end#i-1]，然後檢查區間#i [start#i, end#i] 中的 start#i 有沒有被包括在區間#i-1 (start#i-1 < start#i < end#i-1，在上圖就是 x1 < x3 < x2，但實際上要改用等號才算考慮週詳: start#i-1 < start#i <= end#i-1)，接著再取兩區間中比較大的 end (end#i，以上圖來說就是 x4)，不斷往後重複這個過程(x3 -> x6)直到條件不成立(如上圖 x7 沒有被 [x1, x6] 包括，此時代表數個區間合併完畢，開始新一輪的合併。

情形 2


x1, x3 重疊在一起讓人有些眼花撩亂，這時候要回頭想一下第一步用 binary search 插入 newInterval 時是以 start 還是 end 做為搜尋標的？如果是以 start，就可以保證插入後的結果 start 重疊的區間一定是連續排列，所以只要把情形 1 的作法稍微改一下，區間#i-1與區間#i重疊的檢查改為: start#i-1 <= start#i <= end#i-1，但 start#i-1 <= start#i 或 start#i-1 < start#i 在這兩個步驟都是多餘的(因為已排序)，可簡化為 start#i <= end#i-1。

綜合步驟一與步驟二，可以確定此演算法的時間複雜度為 O(n + log n)

Source Code: C++ 版

?
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int findPos(const vector<Interval>& intervals, const Interval& newInterval){
        int left = 0;
        int right = intervals.size() - 1;
        while(left <= right){
            int middle = (left+right)/2;
            if(intervals[middle].start == newInterval.start){
                return middle;
            }else if(intervals[middle].start > newInterval.start){
                right = middle - 1;
            }else{ //intervals[middle].start < newInterval.start
                left = middle + 1;
            }
        }
         
        return left;
    }
 
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> result;
        if(intervals.size() == 0){
            result.push_back(newInterval);
            return result;
        }
         
        //step1
        const int pos = findPos(intervals, newInterval);
        intervals.insert(intervals.begin() + pos, newInterval);
        //step2
        int start = intervals[0].start;
        int end = intervals[0].end;
        for(int i = 1; i < intervals.size(); ++i){
            if(end >= intervals[i].start){
                //situation1+2
                end = max(intervals[i].end, end);
            }else{
                //merge
                result.push_back(Interval(start, end));
                start = intervals[i].start;
                end = intervals[i].end;
            }
        }
         
         
        result.push_back(Interval(start, end));
        return result;
    }
};

Source Code: C 語言版

會有這個版本的原因是小弟左思右想幾乎不可能有比這個更快的方法了，但 LeetCode 上 C 語言版獨占鰲頭(6ms)，那我就改用 C 語言重作一次試試看，果然這次衝到冠軍了：
?
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 * };
 */
int findPos(struct Interval* intervals, int intervalsSize, int start){
    int left = 0;
    int right = intervalsSize - 1;
    while(left <= right){
        int middle = (left+right)/2;
        if(intervals[middle].start == start){
            return middle;
        }else if(intervals[middle].start > start){
            right = middle - 1;
        }else{ //intervals[middle].start < newInterval.start
            left = middle + 1;
        }
    }
     
    return left;
}
 
 
struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
    struct Interval *result;
    struct Interval *tmp;
    int pos, tmpsize;
    int start, end;
    int i;
     
    if(intervalsSize == 0){
        result = (struct Interval*)malloc(sizeof(struct Interval));
        *result = newInterval;
        *returnSize = 1;
        return result;
    }
     
    //step1
    pos = findPos(intervals, intervalsSize, newInterval.start);
    tmpsize = intervalsSize + 1;
    tmp = (struct Interval*)malloc(sizeof(struct Interval)*tmpsize);
    if(pos == 0){
        memcpy(&tmp[0], &newInterval, sizeof(newInterval));
        memcpy(&tmp[1], intervals, sizeof(intervals[0])*intervalsSize);
    }else if(pos == intervalsSize){
        memcpy(&tmp[0], intervals, sizeof(newInterval)*intervalsSize);
        memcpy(&tmp[intervalsSize], &newInterval, sizeof(newInterval));
    }else{
        memcpy(&tmp[0], &intervals[0], sizeof(intervals[0])*pos);
        memcpy(&tmp[pos], &newInterval, sizeof(newInterval));
        memcpy(&tmp[pos+1], &intervals[pos], sizeof(intervals[0])*(intervalsSize - pos));
    }
     
    //step2
    result = (struct Interval*)malloc(sizeof(struct Interval)*tmpsize);
    start = tmp[0].start;
    end = tmp[0].end;
    for(i = 1, *returnSize = 0; i < tmpsize; ++i){
        if(end >= tmp[i].start){
            end = (tmp[i].end > end ? tmp[i].end : end);
        }else{
            result[*returnSize].start = start;
            result[*returnSize].end = end;
            ++*returnSize;
            start = tmp[i].start;
            end = tmp[i].end;
        }       
    }
     
    free(tmp);
    result[*returnSize].start = start;
    result[*returnSize].end = end;
    ++*returnSize;
    return result;
}

參考資料

本篇解法參考自 LeetCode 56. Merge Intervals 的討論，LeetCode#56,57 只要解出其中一題另外一題就呼之欲出，靈魂機器給出的解法比較難理解。

C 名題精選百則問題 5-18 包含在其他區間中的區間極為類似本題，差異是該題講的是「包含」，而不是「重疊」，不過核心精神也是一樣要先對區間做排序(排序方式略有不同)，可以參考看看，冼鏡光老師解釋的比本文要更加詳盡。
張貼者： 於
標籤： , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)