您當前位置：首頁 > 互聯網 > 區間選點+區間覆蓋

區間選點+區間覆蓋

來源：程序員人生發布時間：2014-11-23 09:17:08 閱讀次數：2722次

區間選點+區間覆蓋

區間選點問題（選擇最少的點，使得每一個區間都最少有k個點）

將這些區間[l,r]先依照r從小到大排序，再依照l從大到小排序。選點盡可能選擇靠近右側界的點。然后依照這個排序后的區間進行遍歷，用1個變量來寄存遍歷進程中上個區間的右側界，然后碰到1個新的區間的時候需要分兩種情況討論：1、這個區間和上個區間有相交的部份，那末就需要判斷1下上次選擇的點有多少在這個區間內，這些點滿足要求嗎？不滿足的話還需要在這個區間內選點2、這個區間和上個區間沒有交集，那末這個區間就需要選點。

上述策略可以保證右側界相同的區間，先選擇區間短的那個。由于短區間的點被選擇了，那末相同右側界的更大的區間肯定包括這個比較小的區間選擇的所有點，這樣這個大點的區間被滿足的可能性就比較大了。并且這里選點的策略是取盡可能靠近右側界的點，這樣選取被滿足區間個數會是最大的。

偽代碼

    interval[maxn][2];
    sort(interval, interval + maxn, cmp);//cmp依照r小l大優先級高來排列

    pre = interval[1][0] - 1;   //制造出不相交的右側界
    for in range(1, maxn):
        if interval[i][0] > pre://不相交
            //靠近右側界選點
        else:
            //先查找這個區間已被選中了多少點,然后根據是不是滿足要求再進行選點
        pre = interval[1][1]； //更新右側界
    else:;

題目：uva10148Advertisement（區間選點）

區間覆蓋問題（選擇最少的區間使得覆蓋[m,n])

假定覆蓋的區間是[m, n].先預先處理掉和[m,n]不沾邊的區間。把出發點小的區間放前面，如果出發點相同的區間就把長的區間放前面。做兩個特判，判斷出發點最早的區間是不是涵蓋m，和最后的覆蓋是不是有覆蓋到n。接著就是中間的判斷了，中間的判斷看代碼吧。

偽代碼

    interval[maxn][2];
    vis[maxn];//記錄哪條邊被選擇
    //刪除和[m, n]不沾邊的區間,并且依照l小r大優先級高排序

    function Cover_Interval:    
        if interval[0][0] < m   //是不是涵蓋m
            return false;
        pre = m;//前1個選擇區間的右側界，也是下個要選擇區間的有效的起始邊界
        t = -1;//記錄前1個區間的下標，由于可能這個區間其實不是最好的區間
        cover = m - 1;//目前已覆蓋了的位置

        for in range(1, maxn):
            if interval[i][0] <= pre: //滿足最少覆蓋到上個區間右側界pre，使得全部覆蓋的區間不會斷開
                if interval[i][1] > cover: //選取最長的滿足上面的要求的區間
                    vis[i] = 1;
                    cover = interval[i][1]; //更新覆蓋位置
                    if t != -1:             //上次選中的取消
                        vis[t] = 0;
            else:                     //不滿足要求說明需要選擇下個新的區間，更新pre
                pre = cover;
                if interval[i][0] > pre: //如果當前這個區間的左側界比覆蓋位置更大，那末說明中間有1段是覆蓋不到的
                    return false;
                t = -1;                  //新的區間清空上次選中
                i--;
            if cover >= n:
                break;
        else:;

        if cover < n
            return false;
        //輸出被選擇的區間according to vis[maxn]
        return true;
    function end;