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);
}
}