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].
這個(gè)題目相當(dāng)于溫習(xí)了一遍快排
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;
? ? }
}
另一個(gè)種排序可以這樣寫：
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;
? ? }
}
