您當(dāng)前位置：首頁(yè) > 互聯(lián)網(wǎng) > 區(qū)間選點(diǎn)+區(qū)間覆蓋

區(qū)間選點(diǎn)+區(qū)間覆蓋

來(lái)源：程序員人生發(fā)布時(shí)間：2014-11-23 09:17:08 閱讀次數(shù)：2726次

區(qū)間選點(diǎn)問(wèn)題（選擇最少的點(diǎn)，使得每一個(gè)區(qū)間都最少有k個(gè)點(diǎn)）

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

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

偽代碼

    interval[maxn][2];
    sort(interval, interval + maxn, cmp);//cmp依照r小l大優(yōu)先級(jí)高來(lái)排列

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

題目：uva10148Advertisement（區(qū)間選點(diǎn)）

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

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

偽代碼

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

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

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

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