題目
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: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
The number of given pairs will be in the range [1, 1000].
分析及解答
【调试】当出现数组指针越界的时候，分清是下标大了还是小了，如果大了，寻找所有让下标上升的地方进行检查。【快排】引入快排后，在leetcode上排名效率前1%。
// 经典题目(任务分配，贪心算法)
public class FindLongestChain {
public int findLongestChain(int[][] pairs) {
if(pairs == null || pairs.length == 0){
return 0;
}
qsort(pairs,0,pairs.length-1);
int result = 1;
int lastEnd = pairs[0][1];
for(int i = 1;i < pairs.length;i++){
if(pairs[i][0] > lastEnd){
result ++;
lastEnd = pairs[i][1];
}
}
return result;
}
// 快排。
public void qsort(int[][] pairs,int start ,int end){
if(start >= end ){
return ;
}
int mid = rangeSort(pairs, start, end);
qsort(pairs, start, mid-1);
qsort(pairs, mid+1, end);
}
public int rangeSort(int[][] pairs,int start,int end){
int p1 = start,p2 = end;
int[] tmp = new int[2];
tmp[0] = pairs[start][0];
tmp[1] = pairs[start][1];
while(p1 < p2){
while(p1 < p2 && pairs[p2][1] > tmp[1]){
p2--;
}
if(p1 < p2){
pairs[p1][0] = pairs[p2][0];
pairs[p1][1] = pairs[p2][1];
p1++;
}
while(p1 < p2 && pairs[p1][1] <= tmp[1]){
p1++;
}
if(p1 < p2){
pairs[p2][0] = pairs[p1][0];
pairs[p2][1] = pairs[p1][1];
p2--;
}
}
pairs[p1][0] = tmp[0];
pairs[p1][1] = tmp[1];
return p1;
}
public static void main(String[] args) {
FindLongestChain flc = new FindLongestChain();
int[][] data ={{-10,-8},{8,9},{-5,0},{6,10},{-6,-4},{1,7},{9,10},{-4,7}};
flc.findLongestChain(data);
System.out.println("end");
}
}
