# Prom Night Quick Sort

QUESTION

The Hexagon University of India will be hosting its Prom Night tonight.There would be M boys and N girls at the prom tonight. Each boy wants a girl who is strictly shorter than him. A girl can dance with only one boy and vice-versa. Given the heights of all the boys and girls tell whether it is possible for all boys to get a girl.\n\nInput: \nThe first line contains T denoting the number of test cases.\nEach test case contains three lines.\nThe first line contains M and N.\nThe second line contains M integers each denoting the height of boy.\nThe third contains N integers each denoting the height of girl.\n\nOutput:\nPrint YES if it is possible for each boy to get a girl else print NO.\n\nConstraints: \n1<=T<=10\n1<=N, M<=10000 \n1<=Height<=200.

“TESTCASE_1”: “1\n4 5\n2 5 6 8\n3 8 5 1 7\n###—###SEPERATOR—###—\nYES”, “TESTCASE_2”: “5\n8 10\n7 167 96 171 25 14 156 6 \n138 33 189 56 161 178 94 72 143 2 \n3 6\n127 80 89 \n110 194 155 159 174 9 \n9 10\n55 189 144 124 46 132 125 77 89 \n12 163 157 85 93 109 89 42 194 32 \n3 10\n89 99 176 \n134 155 191 73 26 142 161 194 140 57 \n2 3\n144 47 \n157 116 113 \n###—###SEPERATOR—###—\nNO\nNO\nNO\nYES\nNO”, “TESTCASE_3”: “10\n2 8\n135 101 \n170 125 79 159 163 65 106 146 \n2 8\n162 92 \n196 143 28 37 192 5 103 154 \n3 3\n22 117 119 \n96 48 127 \n2 9\n70 113 \n68 100 36 95 104 12 123 134 74 \n5 2\n112 54 69 148 45 \n63 158 \n8 10\n124 142 130 179 117 36 191 43 \n89 107 41 143 65 49 47 6 91 130 \n1 1\n7 \n102 \n4 9\n30 24 85 155 \n157 41 167 177 132 109 145 40 27 \n4 8\n139 119 83 130 \n142 34 116 40 59 105 131 178 \n7 4\n187 22 146 125 73 71 30 \n178 174 98 113 \n###—###SEPERATOR—###—\nYES\nYES\nNO\nYES\nNO\nYES\nNO\nNO\nYES\nNO”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````import java.io.*;
import java.util.*;
public class TestClass {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T>0)
{
int n=sc.nextInt();
int m=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
int arr1[]=new int[m];
for(int i=0;i<m;i++)
arr1[i]=sc.nextInt();
sort(arr,0,n-1);
sort(arr1,0,m-1);
if(n<m)
{
int count=0;
for(int i=0;i<n;i++)
{
if(arr[i]>arr1[i])
count++;
}
if(count==n)
System.out.println("YES");
else
System.out.println("NO");
}
else
{
System.out.println("NO");
}
T--;
}
}
static void merge(int arr[],int l,int m,int r)
{
int n1=m-l+1;
int n2=r-m;
int L[]=new int[n1];
int R[]=new int[n2];

for(int i=0;i<n1;i++)
L[i]=arr[l+i];
for(int i=0;i<n2;i++)
R[i]=arr[m+1+i];

int i=0,j=0;

int k=l;
while(i<n1 && j<n2)
{
if(L[i]<=R[j])
{
arr[k++]=L[i++];
}
else
{
arr[k++]=R[j++];
}
}
while(i<n1)
arr[k++]=L[i++];
while(j<n2)
arr[k++]=R[j++];

}
static void sort(int arr[],int l,int r)
{
if(l<r)
{
int m=(l+r)/2;
sort(arr,l,m);
sort(arr,m+1,r);
merge(arr,l,m,r);
}
}
}``````