A list of packets is given with varying sizes and there are n channels. 

 

Each of the n channel must have a single packet 

Each packet can only be on a single channel 

The quality of a channel is described as the median of the packet sizes on that channel. The total quality is defined as sum of the quality of all channels (round to integer in case of float). Given the packets []int32 and channels int32 find the maximum quality. 

 

Example 1: 

 

packets := []int32{1, 2, 3, 4, 5} 

channels := 2 

 

// Explanation: If packet {1, 2, 3, 4} is sent to channel 1, the median of that channel would be 2.5. 

//               If packet {5} is sent to channel 2 its median would be 5.  

//               Total quality would be 2.5 + 5 = 7.5 ~ 8 

answer := 8 

Example 2: 

 

packets := []int32{5, 2, 2, 1, 5, 3} 

channels := 2 

 

// Explaination: Channel 1: {2, 2, 1, 3} (median: 2) 

//               Channel 2: {5, 5}       (median: 5) 

//               Total Quality : 2 + 5 = 7 

 

// Explaination 2: Channel 1: {5, 2, 2, 1, 3} (median: 2) 

//                 Channel 2: {5}             (median: 5) 

//                 Total Quality : 2 + 5 = 7 

answer := 7 

 

 

import java.util.*; 

import java.lang.*; 

import java.io.*; 

import java.util.stream.*; 

 

class Solution 

{ 

public static void main (String[] args) throws java.lang.Exception 

{ 

int packets[] = { 5,2,2,1,5,3 }; 

int channels = 2; 

System.out.println(getQuality(packets, channel)); 

} 

 

private static int getQuality(int[] packets, int channel); 

{ 

int quality = 0; 

Array.sort(packets); 

int index = packets.length - 1; 

for (int i = channel - 1; i >= 1; i--) 

{ 

while (index -1 >= 0 && packets[index] == packets[index -1]) 

index--; 

quality += packets[index]; 

} 

quality += getMedian(packets, 0, index); 

return quality; 

} 

 

private static int getMedian(int[] packets, int start, int end) 

{ 

int length =  (end - start + 1); 

int mid = (start + end)/2; 

if (length %2 == 0) 

{ 

return (packets[mid]+packets[mid+1])/2; 

} 

else 

{ 

return packets[mid]; 

} 

} 

}