CareerCup

public class CanRunTasks {

	public static void main(String[] args) {
		int[][] S = new int[][]{{0, 4}, {1, 3}, {2, 5}, {3, 5}};
		int[][] T = new int[][]{{0, 4}, {1, 2}, {2, 3}};
		
		System.out.println(canRun(S, T, new ArrayList<>(), 0, false));
	}
	
	static boolean canRun(int[][] S, int[][] T, List<Integer> serverIndexes, int taskIndex, boolean canAllocate){
		int[] alloc = allocateATask(S, T, serverIndexes, taskIndex);
		if(alloc[1] <= -1){
			return true;
		}if(alloc[0] <= -1 && alloc[1] > -1){
			return false;
		}
		
		if(T[taskIndex][1] > 0){
			serverIndexes.add(alloc[0]);
			canAllocate = canRun(S, T, serverIndexes, alloc[1], canAllocate);
		}else{
			canAllocate = canRun(S, T, new ArrayList<>(), alloc[1]+1, canAllocate);
		}
		
		return canAllocate;
	}
	
	static int[] allocateATask(int[][] S, int[][] T, List<Integer> serverIndexes, int taskIndex){
		int[] res = new int[2];
		res[0] = -1; res[1] = -1;
			
		int sI = 0;
		while(sI < S.length){
			if(S[sI][1] > 0 && !serverIndexes.contains(sI)){
				res[0] = sI;
				S[sI][1]--;
				break;
			}
			sI++;
		}
		int tI = 0;
		while(tI < T.length){
			if(T[tI][1] > 0){
				res[1] = tI;
				T[tI][1]--;
				break;
			}
			tI++;
		}
		return res;
	}
}

public class Server{
	private int units;
	
	public Server(int u){
		units = u;
	}
}

public boolean canAssign(int[] tasks, int[] servers){
	Stack<Server> st = new Stack<Server>();
	for(int i = 0; i < servers.length; i++){
		st.push(new Server(servers[i]));
	}
	for(int i = 0; i < tasks.length; i++){
		if(tasks[i] > st.size()){
			return false;
		}
		while(tasks[i] > 0){
			Server s = st.pop();
			s.units--;
			if(s.units != 0){
				st.push(s);
			}
			tasks[i]--;
		}
		
	}
	return true;
}

bool CanRunTask(int[] t, int[] s)
{
for (var i = 0; i < t.Length; ++i) {
for (var j = 0; j < s.Length; ++j) {
if (s[j] > 0)
{
--t[i];
--s[j];
if (t[i] == 0) {
break;
}
}
}
if (t[i] > 0) {
return false;
}
}

return true;
}

bool CanRunTask(int[] t, int[] s)
{
for (var i = 0; i < t.Length; ++i) {
for (var j = 0; j < s.Length; ++j) {
if (s[j] > 0)
{
--t[i];
--s[j];
if (t[i] == 0) {
break;
}
}
}
if (t[i] > 0) {
return false;
}
}

return true;
}

bool CanRunTask(int[] t, int[] s)
{          
    for (var i = 0; i < t.Length; ++i) {
        for (var j = 0; j < s.Length; ++j) {
            if (s[j] > 0)
            {
                --t[i];
                --s[j];
                if (t[i] == 0) {
                    break;
                }
            }
        }
        if (t[i] > 0) {
            return false;
        }
    }

    return true;
}

bool CanRunTasks(int[] S, int[] T)
{ 
  List<int> s = new List<int>(S);
  List<int> t = new List<int>(T);
  
  int sc = -1;
  while(s.Count > 0 && t.Count > 0)
  {          
     int u = t.First();
     
     if(u > s.Count)
         return false;
     
     for(int i = 0; i < u; i++)
     {
       sc = (sc + 1) % s.Count;
         
       s[sc]--;    
	   
	   if(s[sc] == 0)
           s.RemoveAt(sc--);
     } 
     
     t.RemoveAt(0);
     
  }
  
  return t.Count == 0;
}

void Main()
{
	Console.WriteLine(CanRunTasks(new [] {2, 1, 1, 1}, new[] { 2, 2, 1 }));
}

Iterate through all the tasks and for each task:
1) If the no of units > the total no of servers return false;
2) Else try and allocate the units to servers 1 at a time and while doing so if we run out of servers then return false.

public class ServerTask {
	
	public static void main(String [] args){
		
		Server s1 = new Server(4);
		Server s2 = new Server(3);
		Server s3 = new Server(2);
		Server s4 = new Server(1);
		
		Server [] servers = {s1,s2,s3,s4};
		
		Task t1 = new Task(4);
		Task t2 = new Task(2);
		Task t3 = new Task(3);
		
		Task[] tasks = {t1,t2,t3};
		
		System.out.println(new ServerTask().canRunTasks(servers, tasks));
		
		
	}
	
	boolean canRunTasks(Server[] servers, Task[] tasks){
		boolean canRun = true;
		
		for(Task task : tasks){
			int noOfUnits = task.totalUnits;
			if(canRun){
				//If the total no of units in a particular task is more than the total no of servers 
				//then the condition of 2 units of the same task cannot run on same server cannot be met.
				if(noOfUnits>servers.length){
					canRun=false;
					break;
				}else{
					int idx =0;
					//Try and allocate the units in the task in 1 server at a time till all the units in the task are allocated.
					while(noOfUnits>0){			
						
						if(servers[idx].allocateSlot()){
							idx++;
							noOfUnits--;
						}else if(idx<servers.length-1){
							idx++;
						}
						else{//If we cannot find a server to allocate then break
							canRun=false;
							break;
						}
					}
						
					
				}
			}else{
				break;
			}
		}
		
		return canRun;
	}

}

class Server{
	int totalSlots;
	int openSlots;
	
	Server(int totalSlots){
		this.totalSlots=totalSlots;
		this.openSlots=totalSlots;
	}
	
	public boolean allocateSlot(){
		if(openSlots>0){
			openSlots--;
			return true;
		}else{
			return false;
		}
		
	}
}

class Task{
	int totalUnits;
	
	Task(int totalUnits){
		this.totalUnits=totalUnits;
	}
}

- Add the servers to a priority queue based on their slot count
- now iterate over the task vector
- assign units to each server by popping the server from priority queue (max slots amongst others)
- decrease this server's slot count and if the remaining slots > 0 store it in a temporary array (do not push back to the queue yet)
- if the priority_queue becomes empty while units of a task are left, then return false
- once the task is done, push all the elements in the temporary array back to the priority queue
- at the end return true

I think all the code so dar are wrong, e.g
S = {1,2,5,5}
T = {4,2,3}

this should work because you allocate 4 to all, 2 to the {5,5} server and 3 to {2,5,5} server but the algo so far would return false

this question is similar to the task question, everytime we want to assign a server to a task we need to find the server with the most slot left, therefore this is a heap question

bool CanRunTasks(vector<int> servers, vector<int> tasks)
{
	sort(servers.begin(), servers.end(), greater<int>());
	sort(tasks.begin(), tasks.end(), greater<int>());
	for (int i = 0; i < tasks.size(); ++i) {
		for (int j = 0; j < servers.size() && tasks[i] > 0; ++j) {
			if (servers[j] > 0) {
				--servers[j];
				--tasks[i];
			}
		}
		if (tasks[i] > 0) {
			return false;
		}
	}
	return true;
}