Hackerrank problem


how to solve this question?

Is not it just a Maximum Bipartite Matching problem?

1 Like

Thanks, it was a bipartite matching problem.

1 Like

i tried a naive approach
By sorting customers list with the height size and also sorted caps list with the height size and traversing the each customer ,if a possible cap size and cost is available if yes the remove the cap from the caps list and increase the count ,continue traversing till the end of the customers list .
But my solution only passes one test cases .

import java.util.;
import java.io.
;
import java.lang.*;
import java.math.BigInteger;

class P implements Comparable


{
int key ;
int value;

    P(int k,int v)
	{
		this.key = k;
		this.value = v;
	}
	int getValue()
	{
		return value;
	}
	int getKey()
	{
		return key;
	}
	
	public int compareTo(P obj)
	{
		return this.value-obj.value ;
	}
   public String toString()
   {
	   return key+ " "+value ;
	   
   }
  /** public int hashCode()
   {
	   return key;
   }**/
	
}

class DesperateHat
{

public static void main(String args[])
{
	Scanner s = new Scanner(System.in);
	
	  
	  		
     	  StringTokenizer st1 = new StringTokenizer(s.nextLine());
		      int N = Integer.parseInt(st1.nextToken());
          	  int M = Integer.parseInt(st1.nextToken());
          ArrayList<P> al = new ArrayList<P>();
		for(int i=0;i<N;i++)
		{
		    StringTokenizer st2 = new StringTokenizer(s.nextLine());
                
		     int r =  Integer.parseInt(st2.nextToken());
		     int e = Integer.parseInt(st2.nextToken());
		  al.add(new P(r,e));
                                                
                        				
		}
		Collections.sort(al);
		
		ArrayList<P> al2 = new ArrayList<P>();
		for(int j=0;j<M;j++)
		{
			StringTokenizer st3 = new StringTokenizer(s.nextLine());
		    int q = Integer.parseInt(st3.nextToken());
		    int w = Integer.parseInt(st3.nextToken());
		  al2.add(new P(q,w));
		}
		//Collections.sort(al2);
		int count = 0;
        for(int y=0;y<al.size();y++)
		{
			for(int u=0;u<al2.size();u++)
			  {	
			    if(al.get(y).getKey()<al2.get(u).getKey()&&al2.get(u).getValue()<=al.get(y).getValue())
			     {
				     count++;
			       // al.remove(al.get(y));
			        al2.remove(al2.get(u));
					
					break;
	          		}
			  }		
		}				
		
		System.out.println(count);
		
						  
 		   
		   
		 
	     		 
}

}