You receive as input n pairs of numbers. In every pair, the first number is smaller than the second one. A chain of pairs (a, b), (c, d) is formed by pairs having c > b. You must find the longest chain of pairs formed by the pairs given to you.
Input: int[][] pairs = {{3,6}, {2,9}, {7,8}}; Output: 2 Explanation: The chain of pairs is: {3, 6}, {7, 8}. |
Solution:
1. public static int findLongestChainOfPairs(int[][] pairs) { 2. Arrays.sort(pairs, Comparator.comparingInt(a -> a[0])); 3. int pairsLength = pairs.length; 4. int[] chainsOfPairs = new int[pairsLength]; 5. Arrays.fill(chainsOfPairs, 1); 6. 7. for (int j = 1; j < pairsLength; ++j) { 8. for (int i = 0; i < j; ++i) { 9. if (pairs[i][1] < pairs[j][0]) 10. chainsOfPairs[j] = Math.max(chainsOfPairs[j], chainsOfPairs[i] + 1); 11. } 12. } 13. 14. int chainOfPairs = 0; 15. for (int chain: chainsOfPairs) { 16. if (chain > chainOfPairs) { 17. chainOfPairs = chain; 18. } 19. } 20. return chainOfPairs; 21. } 22.