tasks scheduled on servers

Reference: http://www.careercup.com/question?id=4847342612119552

There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers? 

Ex: 
Servers capacity limits: 8, 16, 8, 32 
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8 
For this example, the program should say ‘true’. 

Ex2: 
Server capacity limits: 1, 3 
Task capacity needs: 4 
For this example, program should return false.

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM 8
int stack[NUM];
int top = -1;
#if 1
int server_capacity[NUM] = {8, 16, 8, 32};
int task_capacity[NUM] = {18, 4, 8, 4, 6, 6, 8, 8};
int servers = 4;
int tasks = 8;
#else
int server_capacity[NUM] = {1, 3};
int task_capacity[NUM] = {4};
int servers = 2;
int tasks = 1;
#endif

void dump_stack(void)
{
	int task, server;
	int i;

	for (i = 0; i <= top; i++) {
		task = i;
		server = stack[i];
		printf("(task %d(%d) -> server %d(%d))\n", task, task_capacity[task], server, server_capacity[server]);
	}
}

void dump_server(int n)
{
	int i;

	for (i = 0; i < n; i++)
		printf("%d ", server_capacity[i]);
	printf("\n");
}

int backtracing(int servers, int tasks, int s)
{
	int r = 0;
	int i;

	top++;	
	stack[top] = s;
	server_capacity[s] -= task_capacity[top];

	if (server_capacity[s] < 0)
		goto exit;

	if (top == tasks-1) {
		r = 1;
		goto exit;
	}

	for (i = 0; i < servers; i++) {
		r = backtracing(servers, tasks, i);
		if (r)
			break;
	}

exit:
	server_capacity[s] += task_capacity[top];
	top--;

	return r;
}

int main()
{
	int i;

	for (i = 0; i < servers; i++) {
		if (backtracing(servers, tasks, i)) {
			printf("true\n");
			dump_server(servers);
			top = tasks-1;
			dump_stack();
		}
	}

	return 0;
}

 

Leave a Reply