646. Maximum Length of Pair Chai
646. Maximum Length of Pair Chain
找到符合规则的最长chain。
weekly contest 42的第二题。
我一看感觉很简单，就是dfs，但是总也写不出，各种Wrong Answer。
最后想了一下，这个就是类似Permutation的「排列」问题。晚上整理了一下，写了下面的代码，总算不Wrong Answer了，但是TLE了，不过思路是比较清晰的：
我的DFS解法（TLE）:
//注意，以下代码会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了，就说明有可以优化的地方。
这题有个条件是In every pair, the first number is always smaller than the second number. 这说明，如果我们以第一个数字排序，那后一个数组[a,b]的第二个数字(b)是一定大于前一个数组[c,d]的的第一个数字(c)的。这样可以减少很多次递归。
优化了一下：
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确实非常大，用DFS的话栈深度不可想象。
看了下大家的discussion，有两种算法，一种是Greedy，说是跟CLRS上的activity selection几乎一模一样（还有interval 问题）。。顿时觉得自己基础差。
另一种是DP。今天先到这儿了。
--
26 July Update
GREEDY(ITERATION)
复习了一下activity selection问题，发现这题跟那个几乎是一致的。写了一下代码，但是我其实并不能说服自己greedy得到的答案就是正确的，这一点跟dp不太一样，dp是有理有据的，而greedy仿佛是需要证明的，据说greedy经常用剪枝来证明，fine，又一个我认识他他不认识我的名词。。今天先到这，这题还没完。
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)
看了算法导论上的活动选择问题，这题还可以用递归来做，或者说，所有的for循环都能改成递归？
这题的递归实现：
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有点浪费了，它这个方法跟Weighted Job Scheduling Dynamic Programming的思路是一致的，工作安排比这个多一个要考虑的地方，就是不同的工作既要不冲突，而且因为每份工作的报酬不一样，不能简单地只考虑完成时间最短，所以只能用DP。那这题跟Job Schedule唯一的不同就是在if判断的地方，这题是dp[i] < dp[j] + 1，如果是Job Schedule就要是dp[i] < dp[j] + profit[i]。
两重循环的解法让人想起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，为什么按照开始时间和结束时间sort都能AC，不sort就无法AC?
另外，这题的GREEDY，我还是不太懂得如何证明，算法导论上有证明，我没细看。据说通常用剪枝证明GREEDY。
ref:
http://www.cnblogs.com/hapjin/p/5573419.html
http://www.jianshu.com/p/293a4056a50a
