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