As per question I Made a Heap which gives me both max and min value. Since there is always two value available so there is no need to handle that.
My code looks like
static ArrayList<Integer> pq;
public static void main(String[] argh) throws Exception{
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
pq= new ArrayList<>();
long sum= 0;
String[] inp= br.readLine().trim().split(" ");
// int n= br.nextInt();
int n= Integer.parseInt(inp[0]);
int k;
for(int nn=0; nn<n; nn++){
String[] inpK= br.readLine().trim().split(" ");
// k= br.nextInt();
k= Integer.parseInt(inpK[0]);
int num, pos;
if(k != 0){
for(int kk=0; kk<k; kk++){
// num= br.nextInt();
num= Integer.parseInt(inpK[kk+1]);
pos= getPosByBS(num);
pq.add(pos, num);
}
}
int max= pq.get(pq.size() - 1);
pq.remove(pq.size() - 1);
int min= pq.get(0);
pq.remove(0);
sum += (long)(max-min);
}
System.out.println(sum);
}
private static int getPosByBS(int val){
if(pq.size() == 0) return 0;
int l= 0;
int h= pq.size() - 1;
int mid;
while(l<=h){
mid= (l+h)>>1;
if(pq.get(mid) > val) h= mid-1;
else if(pq.get(mid) < val) l= mid+1;
else return mid;
}
return l;
}
On submission it gives me TLE. I found few c++ solutions all of them looks more or less same. So why am I getting TLE?