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
