You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:
Input:[[1,2], [2,3], [3,4]]Output:2Explanation:The longest chain is [1,2] -> [3,4]
Note:
The number of given pairs will be in the range [1, 1000].
这个题目相当于温习了一遍快排
class Solution {
public int findLongestChain(int[][] pairs) {
if (pairs.length == 0) return 0;
qsort(pairs, 0, pairs.length - 1);
int end = pairs[0][1];
int len = 1;
for (int i = 1; i < pairs.length; i++) {
int[] pair = pairs[i];
if (pair[0] > end) {
end = pair[1];
len++;
}
}
return len;
}
private void qsort(int[][] pairs, int left, int right) {
if (left >= right) return;
int pivot = right, l = left;
for (int r = l; r < pivot; r++) {
if (pairs[r][1] < pairs[pivot][1]) {
swap(pairs, l, r);
l++;
}
}
swap(pairs, l, pivot);
qsort(pairs, left, l - 1);
qsort(pairs, l + 1, right);
}
private void swap(int[][] pairs, int i, int j) {
int[] tmp = pairs[i];
pairs[i] = pairs[j];
pairs[j] = tmp;
}
}
另一个种排序可以这样写：
class Solution {
public int findLongestChain(int[][] pairs) {
if (pairs.length == 0) return 0;
qsort(pairs, 0, pairs.length - 1);
int end = pairs[0][1];
int len = 1;
for (int i = 1; i < pairs.length; i++) {
int[] pair = pairs[i];
if (pair[0] > end) {
end = pair[1];
len++;
}
}
return len;
}
private void qsort(int[][] pairs, int left, int right) {
if (left >= right) return;
// System.out.printf("left: %d, right: %d", left, right);
int l = left, r = right, pivot = left;
while (l < r) {
while (pairs[r][1] >= pairs[pivot][1] && r > l) r--;
while (pairs[l][1] <= pairs[pivot][1] && l < r) l++;
swap(pairs, l, r);
}
swap(pairs, pivot, r);
qsort(pairs, left, l - 1);
qsort(pairs, l + 1, right);
}
private void swap(int[][] pairs, int i, int j) {
int[] tmp = pairs[i];
pairs[i] = pairs[j];
pairs[j] = tmp;
}
}
