In this HackerRank Team Formation problem solution For an upcoming programming contest, Roy is forming some teams from the students of his university. A team can have any number of contestants.
Roy knows the skill level of each contestant. To make the teams work as a unit, he forms the teams based on some rules. Each of the team members must have a unique skill level for the team. If a member's skill level is x[i] where 0 < i, there exists another team member whose skill level is x[i] - 1. Note that a contestant can write buggy code and thus can have a negative skill level.
The more contestants on the team, the more problems they can attempt at a time so Roy wants to form teams such that the smallest team is as large as possible.
Problem solution in Python.
from collections import Counter
def smallest_set(start, end, c):
d = {}
d[start - 1] = []
for i in range(start, end + 1):
d[i] = []
prev_len = len(d[i-1])
new_lists = c[i] - prev_len
if new_lists > 0:
d[i] = [1]*new_lists
if prev_len > 0:
num_appends = min(prev_len, new_lists + prev_len)
d[i-1].sort()
d[i] += [x+1 for x in d[i-1][:num_appends]]
d[i-1] = d[i-1][num_appends:]
ans = d[end][0]
for i in range(start, end + 1):
if len(d[i]) > 0:
ans = min(ans, min(d[i]))
if ans == 1:
return 1
return ans
def find_lowest_range(l, n):
c = Counter(l)
i = 0
mini = n
while i < len(l):
end = i
while end < n and (l[i] == l[end] or (l[end] - l[end - 1]) <= 1):
end += 1
end -= 1
if end == i:
return 1
mini = min(mini, smallest_set(l[i], l[end], c))
if mini == 1:
return 1
i = end + 1
return mini
t = int(input())
for _ in range(t):
l = list(map(int, input().split()))
if l[0] == 0:
print(0)
continue
n = l[0]
l = sorted(l[1:])
print(find_lowest_range(l, n))Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int queries = in.nextInt();
while (queries-- > 0) {
teams.clear();
int count = in.nextInt();
int[] arr = new int[count];
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < count; i++) {
arr[i] = in.nextInt();
list.add(arr[i]);
}
Collections.sort(list);
for (int i : list) {
addItem(i);
}
int min = count;
for (Team team : teams) {
if (min > team.getSize()) {
min = team.getSize();
}
}
System.out.println(min);
}
}
static ArrayList<Team> teams = new ArrayList<>();
private static void addItem(Integer item) {
Team sTeam = null;
int index = teams.size();
while (--index >= 0 && teams.get(index).getHigh() > item - 2) {
Team team = teams.get(index);
if (team.getHigh() + 1 == item) {
if (sTeam == null || sTeam.getSize() > team.getSize()) {
sTeam = team;
}
}
}
if (sTeam == null) {
sTeam = new Team();
sTeam.setLow(item);
teams.add(sTeam);
}
sTeam.setHigh(item);
}
private static class Team {
int low;
int high;
public int getLow() {
return low;
}
public void setLow(int low) {
this.low = low;
}
public int getHigh() {
return high;
}
public void setHigh(int high) {
this.high = high;
}
public int getSize() {
return high - low + 1;
}
public boolean isPresent(Integer item) {
if (high >= item && low <= item) {
return true;
}
return false;
}
@Override
public String toString() {
return "[" + low + "," + high + "]";
}
}
}
Problem solution in C++.
using namespace std;
#include <bits/stdc++.h>
#define sgn(x,y) ((x)+eps<(y)?-1:((x)>eps+(y)?1:0))
#define rep(i,n) for(auto i=0; i<(n); i++)
#define mem(x,val) memset((x),(val),sizeof(x));
#define rite(x) freopen(x,"w",stdout);
#define read(x) freopen(x,"r",stdin);
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define sqr(x) ((x)*(x))
#define pb push_back
#define clr clear()
#define inf (1<<28)
#define ins insert
#define xx first
#define yy second
#define eps 1e-9
typedef long long i64;
typedef unsigned long long ui64;
typedef string st;
typedef vector < int > vi;
typedef vector < st > vs;
typedef map < int , int > mii;
typedef map < st , int > msi;
typedef set < int > si;
typedef set < st > ss;
typedef pair < int , int > pii;
typedef vector < pii > vpii;
#define mx 0
int main(){
ios_base::sync_with_stdio(0);
int test;
cin >> test;
while( test-- ){
map< int , priority_queue<int,vi,greater<int> > > val;
int n;
cin >> n;
vi vec(n);
rep(i,n){
int temp;
cin >> temp;
vec[i] = temp;
}
sort(all(vec));
rep(i,n){
int temp = vec[i];
int now = 0;
auto it = val.find( temp-1 );
if( it!=val.end() )
if( it->yy.size() ) {
now = it->yy.top();
it->yy.pop();
}
now++;
val[ temp ].push( now );
}
int ans = INT_MAX;
for( auto x : val )
if( x.second.size() ) ans = min( ans , x.second.top() );
if( ans >= INT_MAX ) ans = 0;
cout<<ans<<endl;
}
}Problem solution in C.
#include<stdio.h>
void merge(int a[],int low,int p,int high)
{
int n,m,i,j,k,c[100000];
n=p-low+1;
m=high-p;
if(n>0 || m>0)
{
i=low;
j=p+1;
k=low;
//printf("%d %d\n",n,m);
while(i<=p && j<=high)
{
while(a[i]<=a[j] && i<=p && j<=high)
{
c[k++]=a[i++];
}
while(a[i]>=a[j] && i<=p && j<=high)
{
c[k++]=a[j++];
}
}
if(i<=p)
{
while(i<=p)
{
c[k++]=a[i++];
}
}
if(j<=high)
{
while(j<=high)
{
c[k++]=a[j++];
}
}
for(i=low;i<=high;i++)
{
a[i]=c[i];
//printf("%d ",a[i]);
}
//printf("\n");
}
else
{
return;
}
}
void mergesort(int a[],int low,int high)
{
int p,i;
if(high>low)
{
p=(low+high)/2;
mergesort(a,low,p);
mergesort(a,p+1,high);
//printf("here is the %d %d %d\n",low,p,high);
merge(a,low,p,high);
}
else
{
return;
}
}
int main()
{
int a[100000],i,n,b[100010],precount,count,j,k,counter,t,t1=0,min;
scanf("%d",&t);
while(t1<t)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
mergesort(a,0,n-1);
precount=0;
count=0;
j=-1;
for(i=0;i<n+10;i++)
{
b[i]=0;
}
i=0;
while(i<n-1)
{
if(a[i]==a[i+1])
{
count++;
}
else
{
count++;
if(count<=precount)
{
k=j;
}
else // count>precount
{
j+=count-precount;
k=j;
}
counter=0;
while(counter<count)
{
b[k--]++;
counter++;
}
precount=count;
count=0;
if(a[i]!=(a[i+1]-1))
{
precount=0;
}
}
i++;
}
for(i=0;i<=j;i++)
{
//printf("%d %d\n",i,b[i]);
}
//printf("after\n");
if(n>1)
{
if(a[n-2]==a[n-1])
{
count++;
if(count<=precount)
{
k=j;
}
else // count>precount
{
j+=count-precount;
k=j;
}
counter=0;
while(counter<count)
{
b[k--]++;
counter++;
}
}
else if(a[n-2]==a[n-1]-1)
{
b[j]++;
}
else
{
b[++j]++;
}
}
min=1000000000;
for(i=0;i<=j;i++)
{
//printf("%d %d\n",i,b[i]);
if(min>b[i])
{
min=b[i];
}
}
if(n==0)
{
min=0;
}
if(n==1)
{
min=1;
}
printf("%d\n",min);
t1++;
}
return 0;
}
0 Comments