top of page
Caută
Poza scriitoruluioanaunciuleanu

Maximum Length Chain of Pairs in JAVA

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.

4 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no...

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Comentários


bottom of page