About
More about me
Blogs
Blog contributions
AI-ML
Buzz-word of current times - AI/ML
Design
System Design
Contact
Contact Us
Max length chain
Max length chain

You are given N pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. You have to find the longest chain which can be formed from the given set of pairs.  

Example 1:

Input:N = 5P[] = {5  24 , 39 60 , 15 28 , 27 40 , 50 90}Output: 3Explanation: The given pairs are { {5, 24}, {39, 60},{15, 28}, {27, 40}, {50, 90} },the longest chain thatcan be formed is of length 3, and the chain is{{5, 24}, {27, 40}, {50, 90}}

Example 2:

Input:N = 2P[] = {5 10 , 1 11}Output: 1Explanation:The max length chain possible is only oflength one.

Obvious Approach

Looking at the problem, seems like more of a graph problem where traversal needs to start from one node and look for possible next nodes. Here, in this traversal we are looking to go for depth to identify the chain. So, traversal method applied here would be DFS.

With this approach lets look at a possible code:

  1. class GfG  
  2. {  
  3.     int maxChainLength(Pair arr[], int n, int u, boolean visited[]) {  
  4.         if (u>=n) return 0;  
  5.           
  6.         visited[u] = true;  
  7.         int max = 1;  
  8.         for (int v=0;v<n;v++) {  
  9.             if (!visited[v] && (arr[u].y <arr[v].x)) {  
  10.                 max = Math.max(max, maxChainLength(arr, n, v, visited)+1);  
  11.             }  
  12.         }  
  13.         visited[u] = false;  
  14.         return max;  
  15.           
  16.     }  
  17.     int maxChainLength(Pair arr[], int n)  
  18.     {  
  19.         if (n==0) return 0;  
  20.         if (n==1) return 1;  
  21.   
  22.         int max = 0;  
  23.         for (int i=0;i<n;i++) {  
  24.             max = Math.max(maxChainLength(arr, n, i, new boolean[arr.length]), max);  
  25.         }  
  26.         return max;  
  27.     }  
  28. }  

Efficiency of a DFS algorithm is O(V+E) , where V represents the number of vertices and E represents the number of edges.

In current case, V=n and E=n-1. So efficiency would be O(n+n-1) = O(2n) ~= O(n) for each iteration. As this iteration is repeated for each element (or V), overall efficiency would be O(n*n) = O(n^2)

Can we look for an approach to improve this efficiency? 

Next Approach

Analytically looking at the problem, position of an element is of no importance. So, we can possibly look at reordering them such that identifying the chain is simplified. Lets sort this array. Important factor here to identify the parameter on the basis of which this array can be sorted. Lets look at the examples to identify any possible pattern:

Ex: { {5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }

Looking at the pair as a<b and c<d, if b<d only then there can be possibility of chain. In above example, {15, 28} cannot be followed up by {17, 19}.

Based on this info if the array is sorted, it would look like following array:

{ {5, 24}, {15, 28}, {27, 40},  {39, 60}, {50, 90} }

Now, in current state single pass iteration from 0th index would help us identify the max chain size. As array is sorted, an ahead index need not look back at a previous index element.

Lets code this approach:


  1. class GfG  
  2. {  
  3.     int maxChainLength(Pair arr[], int n)  
  4.     {  
  5.         if (n==0) return 0;  
  6.         if (n==1) return 1;  
  7.   
  8.         Arrays.sort(arr, (a,b)->a.y-b.y);  
  9.   
  10.         int max=1;  
  11.         int y = arr[0].y;  
  12.         for (int i=1;i<n;i++) {  
  13.             if (arr[i].x>y) {  
  14.                 max++;  
  15.                 y = arr[i].y;  
  16.             }  
  17.         }  
  18.           
  19.         return max;  
  20.     }  
  21. }  

Now with this approach efficiency of sorting is O( n log(n) ) . Also, for the single pass using for loop efficiency is O(n) .

So, overall efficiency of this second approach is O( n log(n) ). 


Final Code Block

Author:   

ankzz