本文主要是介绍leetcode - 646. Maximum Length of Pair Chain 【贪心 + 快排的应用+ 任务调度问题】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
題目
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");}
}这篇关于leetcode - 646. Maximum Length of Pair Chain 【贪心 + 快排的应用+ 任务调度问题】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
