646. Maximum Length of Pair Chain

646. Maximum Length of Pair Chain
找到符合規(guī)則的最長chain咐吼。
weekly contest 42的第二題。
我一看感覺很簡(jiǎn)單商佑,就是dfs锯茄,但是總也寫不出,各種Wrong Answer茶没。
最后想了一下肌幽,這個(gè)就是類似Permutation的「排列」問題。晚上整理了一下抓半,寫了下面的代碼喂急,總算不Wrong Answer了,但是TLE了笛求,不過思路是比較清晰的:

我的DFS解法(TLE):

//注意廊移,以下代碼會(huì)TLE:
    int max = 1;

    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        chainDfs(pairs, new boolean[pairs.length], 0, Integer.MIN_VALUE);
        return max;
    }

    private void chainDfs(int[][] pairs, boolean[] used, int count, int b) {
//不需要terminator
        for (int i = 0; i < pairs.length; i++) {
            if (!used[i] && pairs[i][0] > b) {
                used[i] = true;
                max = Math.max(count + 1, max);
                chainDfs(pairs, used, count + 1, pairs[i][1]);
                used[i] = false;
            }
        }
    }

既然TLE了,就說明有可以優(yōu)化的地方探入。
這題有個(gè)條件是In every pair, the first number is always smaller than the second number. 這說明狡孔,如果我們以第一個(gè)數(shù)字排序,那后一個(gè)數(shù)組[a,b]的第二個(gè)數(shù)字(b)是一定大于前一個(gè)數(shù)組[c,d]的的第一個(gè)數(shù)字(c)的蜂嗽。這樣可以減少很多次遞歸苗膝。

優(yōu)化了一下:


    int max = 1;

    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
//      Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        chainDfs(0, pairs, new boolean[pairs.length], 0, Integer.MIN_VALUE);
        return max;
    }

    private void chainDfs(int index, int[][] pairs, boolean[] used, int count, int b) {
        if (index == pairs.length)
            return;
        for (int i = index; i < pairs.length; i++) {
            if (!used[i] && pairs[i][0] > b) {
                used[i] = true;
                max = Math.max(count + 1, max);
                chainDfs(i + 1, pairs, used, count + 1, pairs[i][1]);
                used[i] = false;
            }
        }
    }

可是萬萬沒想到,仍然TLE...test case確實(shí)非常大徒爹,用DFS的話棧深度不可想象荚醒。

看了下大家的discussion,有兩種算法隆嗅,一種是Greedy界阁,說是跟CLRS上的activity selection幾乎一模一樣(還有interval 問題)。胖喳。頓時(shí)覺得自己基礎(chǔ)差泡躯。

另一種是DP。今天先到這兒了丽焊。

--

26 July Update

GREEDY(ITERATION)

復(fù)習(xí)了一下activity selection問題较剃,發(fā)現(xiàn)這題跟那個(gè)幾乎是一致的。寫了一下代碼技健,但是我其實(shí)并不能說服自己greedy得到的答案就是正確的写穴,這一點(diǎn)跟dp不太一樣,dp是有理有據(jù)的雌贱,而greedy仿佛是需要證明的啊送,據(jù)說greedy經(jīng)常用剪枝來證明偿短,fine,又一個(gè)我認(rèn)識(shí)他他不認(rèn)識(shí)我的名詞馋没。昔逗。今天先到這,這題還沒完篷朵。

    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        int count = 1;
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int index = 0;
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > pairs[index][1]) {
                count++;
                index = i;
            }
        }
        return count;
    }

27 July Update

GREEDY(RECURSION)

看了算法導(dǎo)論上的活動(dòng)選擇問題勾怒,這題還可以用遞歸來做,或者說声旺,所有的for循環(huán)都能改成遞歸笔链?
這題的遞歸實(shí)現(xiàn):

    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        Arrays.sort(pairs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        recursion(pairs, 0);
        return cnt;
    }

    int cnt = 1;

    private void recursion(int[][] pairs, int index) {
        int m = index + 1;
        while (m < pairs.length && pairs[index][1] >= pairs[m][0]) {
            m++;
        }
        if (m < pairs.length) {
            cnt++;
            recursion(pairs, m);
        }
    }

DP

看了另外有人用DP做的,但是這題用DP有點(diǎn)浪費(fèi)了艾少,它這個(gè)方法跟Weighted Job Scheduling Dynamic Programming的思路是一致的卡乾,工作安排比這個(gè)多一個(gè)要考慮的地方翼悴,就是不同的工作既要不沖突缚够,而且因?yàn)槊糠莨ぷ鞯膱?bào)酬不一樣,不能簡(jiǎn)單地只考慮完成時(shí)間最短鹦赎,所以只能用DP谍椅。那這題跟Job Schedule唯一的不同就是在if判斷的地方,這題是dp[i] < dp[j] + 1古话,如果是Job Schedule就要是dp[i] < dp[j] + profit[i]雏吭。
兩重循環(huán)的解法讓人想起LIS PROBLEM(JOB SCHEDULE跟LIS的判斷方法一模一樣)。

public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        
        int i, j, max = 0, n = pairs.length;
        int dp[] = new int[n];
      
        for (i = 0; i < n; i++) dp[i] = 1;
        
        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (pairs[i][0] > pairs[j][1] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;

        for (i = 0; i < n; i++) if (max < dp[i]) max = dp[i];
        
        return max;
    }
}

疑問:用DP為什么要sort陪踩,為什么按照開始時(shí)間和結(jié)束時(shí)間sort都能AC杖们,不sort就無法AC?

另外,這題的GREEDY肩狂,我還是不太懂得如何證明摘完,算法導(dǎo)論上有證明,我沒細(xì)看傻谁。據(jù)說通常用剪枝證明GREEDY孝治。

ref:
http://www.cnblogs.com/hapjin/p/5573419.html
http://www.reibang.com/p/293a4056a50a

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市审磁,隨后出現(xiàn)的幾起案子谈飒,更是在濱河造成了極大的恐慌,老刑警劉巖态蒂,帶你破解...
    沈念sama閱讀 223,126評(píng)論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件杭措,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡钾恢,警方通過查閱死者的電腦和手機(jī)手素,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門吕喘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人刑桑,你說我怎么就攤上這事氯质。” “怎么了祠斧?”我有些...
    開封第一講書人閱讀 169,941評(píng)論 0 366
  • 文/不壞的土叔 我叫張陵闻察,是天一觀的道長。 經(jīng)常有香客問我琢锋,道長辕漂,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,294評(píng)論 1 300
  • 正文 為了忘掉前任吴超,我火速辦了婚禮钉嘹,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘鲸阻。我一直安慰自己跋涣,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,295評(píng)論 6 398
  • 文/花漫 我一把揭開白布鸟悴。 她就那樣靜靜地躺著陈辱,像睡著了一般。 火紅的嫁衣襯著肌膚如雪细诸。 梳的紋絲不亂的頭發(fā)上沛贪,一...
    開封第一講書人閱讀 52,874評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音震贵,去河邊找鬼利赋。 笑死,一個(gè)胖子當(dāng)著我的面吹牛猩系,可吹牛的內(nèi)容都是我干的媚送。 我是一名探鬼主播,決...
    沈念sama閱讀 41,285評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼蝙眶,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼季希!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起幽纷,我...
    開封第一講書人閱讀 40,249評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤式塌,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后友浸,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體峰尝,經(jīng)...
    沈念sama閱讀 46,760評(píng)論 1 321
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,840評(píng)論 3 343
  • 正文 我和宋清朗相戀三年收恢,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了武学。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片祭往。...
    茶點(diǎn)故事閱讀 40,973評(píng)論 1 354
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖火窒,靈堂內(nèi)的尸體忽然破棺而出硼补,到底是詐尸還是另有隱情,我是刑警寧澤熏矿,帶...
    沈念sama閱讀 36,631評(píng)論 5 351
  • 正文 年R本政府宣布已骇,位于F島的核電站,受9級(jí)特大地震影響票编,放射性物質(zhì)發(fā)生泄漏褪储。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,315評(píng)論 3 336
  • 文/蒙蒙 一慧域、第九天 我趴在偏房一處隱蔽的房頂上張望鲤竹。 院中可真熱鬧,春花似錦昔榴、人聲如沸辛藻。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽揩尸。三九已至蛹屿,卻和暖如春屁奏,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背错负。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評(píng)論 1 275
  • 我被黑心中介騙來泰國打工坟瓢, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人犹撒。 一個(gè)月前我還...
    沈念sama閱讀 49,431評(píng)論 3 379
  • 正文 我出身青樓折联,卻偏偏與公主長得像,于是被迫代替她去往敵國和親识颊。 傳聞我的和親對(duì)象是個(gè)殘疾皇子诚镰,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,982評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容