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.

HackerRank Team Formation problem solution

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))

{“mode”:”full”,”isActive”:false}

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 + "]";
		}
	}
}

{“mode”:”full”,”isActive”:false}

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;
}
                    

{“mode”:”full”,”isActive”:false}