Compare 2 team strength and find the wining probability

Question

TeamA = {3,6,7,5,3,5,6,2,9,1} 
TeamB = {2,7,0,9,3,6,0,6,2,6}

print the maximum number of fights TeamA can win if they go to fight in an optimal manner. Consider each number in array is a member and that member fight against another member of other team. For e.g TeamA[i] will fight with TeamB[i] and TeamA[i] wins if it is greater than TeamB. With the given array order of TeamA will win only 4 one to one fight. If we re-arrange TeamA array, there is possibility to win 7 fights.i.e TeamA==> {3,9,1,5,5,7,2,6,3,6}

Below is the code which determines the output correctly but there is complexity in time due to sorting, Please help me to optimize the below code

import java.io.*;
import java.util.*;
public class FightCode{

    // static long[] result ={};
    public static void main(String args[] ) throws Exception {
        Scanner scanner = new Scanner(System.in); 
        try {
            int testCount = scanner.nextInt();

            for (int test=0;test<testCount;test++) {
                int totalMem = scanner.nextInt();     
                Long[] teamA = new Long[totalMem];      
                Long[] teamB = new Long[totalMem]; 
                if (totalMem <1)
                    return;  
                for (int r = 0; r < totalMem; r++) {       
                    teamA[r] = (Long)scanner.nextLong();    
                } 
                for (int i = 0; i < totalMem; i++) {       
                    teamB[i] = (Long)scanner.nextLong();    
                } 
                int count = 0;    

                // int[]swapar = new int[totalMem];  

                Arrays.sort(teamB, Collections.reverseOrder());  
                Arrays.sort(teamA, Collections.reverseOrder()); 
                boolean result = Arrays.equals(teamA, teamB);
                if (result)
                    return;  
                //  System.out.println(Arrays.toString(teamB));
                // System.out.println(Arrays.toString(teamA));   
                for (int a = 0; a < totalMem; a++) {     
                    for (int k=0;k<totalMem;k++) {
                        if(teamA[k] > teamB[a]){
                            // swapar[a] = teamA[k];
                            teamA[k] = 0L;
                            count++;
                            break;
                        } 
                    }  
                } 

                //  System.out.println(Arrays.toString(swapar));
                System.out.println(count);
            }
        } catch(Exception e) {
            System.err.println(e.getStackTrace().toString());
        } finally {
            scanner.close();
        }
    }
}

Answer 1

This question was asked on techgig Code Gladiator 2020. Instead of looping over entire team B in range 0 to k-1, you can loop between x and k-1 , where x is last index in team B where last match was found.

                for (int a = 0; a < totalMem; a++) {     
                for (int k=minIndex;k<a-1;k++) {
                    if(teamA[a] > teamB[k]){
                        // swapar[a] = teamA[k];
                        minIndex=k+1;
                        count++;
                        break;
                    } 
                }  
            }