We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
For those struggling, consider a skill value x, and teams with a max value of skills x-1
if there's no x-1, x must start a new team
if there's more than 1 x-1, then should append x to the smallest team
Solution
sort
prepare a map[s][l] (or HashMap, whatever within the space limit), numbers of previous teams of which the max is s and length is l
for every skill[i], if (map[skill[i]-1]) exists and the smallest length is len*, do map[skill[i]-1][len]--, map[skill[i]][len+1]++
if not, do map[skill[i]][1]++
the result is min(for every map[skill][len]>0 ---> len)
Optimization
as you sorted skill list, for every skill, if map[skill-1] does not exist, then every map[0~skill-2] will never be any longer, thus you actually need a map, just maintain 2 list of length's
use heap(or PriorityQueue) get the smallest length instead of list or array
In java, please use BufferedReader, NOT SCANNER, which would help you save a lot of run time
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Team Formation
You are viewing a single comment's thread. Return to all comments →
For those struggling, consider a skill value x, and teams with a max value of skills x-1
Solution
Optimization