Algorithm筆記 10.4 - greedy演算法練習: 最少停留點問題

如果你也在修Coursera Algorithm Toolbox的話，這是解答！請斟酌使用

問題定義

有一棟建築物住了n個人，每個人在家的時間都不一樣（可能有重疊），如何能最少次抵達此建築物而能拜訪所有人？

這個問題可以map成數線上的線段和點，假設有3個人，在家的時段分別為(1點~3點), (2點~5點), (3點~6點），則在數線上表示

0 [1 [2 [3] 4 5] 6] 7 8 9 10 ....

由上圖來推論，我們可以假設safe move為“從最左邊的區間終點a找起（上圖為3），包含a的區間都能用a來表示可以拜訪的時段”。

證明safe move

假設某optimal solution中，最左邊的區間終點y屬於線段（x,y)，且y不屬於任何線段的代表點：

1. 某線段(w,z)終點z >= y，且此線段包含y，可以用y表示，則optimal solution會減少1。

_ _ （x _ _ _ y） _ _ z） _

2. 某線段終點z <=y，不成立，因為y是最左邊的區間終點。

3. 某線段(w,z) 終點z > y，且w > y，y不能代表(w,z)，不改變optimal solutoin。


以上三種情況包含了任意線段與y所有可能的關係，故根據1. 選擇y為代表點是符合optimal solution，此策略為safe move。

演算法

private static int[] optimalPoints(Segment[] segments) {

    ArrayList<Integer> result = new ArrayList<>();

    //O(nlogn) sort segments ascendingly based on end point    
    Arrays.sort(segments, new Comparator<Segment>() {
        @Override        
        public int compare(Segment o1, Segment o2) {
            return o1.end - o2.end;
        }
    });

    //O(n)    
    int leftmostEnd = segments[0].end;
    for(int i = 0; i < segments.length; i++) {
        if (segments[i].contains(leftmostEnd))
            continue;
        else {
            result.add(leftmostEnd);
            leftmostEnd = segments[i].end;
        }
    }

    //add the last match    
    result.add(leftmostEnd);

    int[] r = new int[result.size()];
    for (int i = 0; i < r.length; i++)
        r[i] = result.get(i);

    return r;
}