HackerRank Team Formation problem solution

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 %dn",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 %dn",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 %dn",i,b[i]);
    }
    //printf("aftern");
    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 %dn",i,b[i]);
        if(min>b[i])
        {
            min=b[i];
        }
    }
    if(n==0)
    {
        min=0;    
    }
    if(n==1)
    {
        min=1;
    }
    printf("%dn",min);
    t1++;
    }
    return 0;
}