Servers And Tasks

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
Flipkart limited

Problem statement

You are given ‘N’ servers and ‘M’ tasks. You are also given two arrays, ‘servers’ and ‘tasks’, where ‘server[i]’ represents the memory limit of i-th server, and ‘task[i]’ represents the memory required to schedule the i-th task. A server can be assigned multiple tasks as long as the limit is not exceeded. Your task is to check whether all the tasks can be scheduled or not.

For example: 
You are given N = ‘3’, M = ‘5’.
servers = { 8, 8, 32 }
tasks = { 4, 4, 8, 12, 16 }
The answers will be true because :
Task 1 and task 2 can be assigned to server 1.
Task 3 can be assigned to server 2.
Task 4 and task 5 can be assigned to server 3.
In this way, we can schedule all the given tasks.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of servers and tasks, respectively.

The second line of each test case contains ‘N’ space-separated integers denoting the memory limit of each server.

The third line of each test case contains ‘M’ space-separated integers denoting the memory required to assign each task.
Output Format: 
For each test case, print “true” if all the tasks can be scheduled. Otherwise, print “false”.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 10 
1 <= N, M  <= 8
1 <= servers[i] <= 10^9
1 <= tasks[i] <= 10^9

Time limit: 1 sec
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Sample Input 1:
2
3 5
8 8 32
4 4 8 12 16
2 1
2 5 
8
Sample Output 1:
true
false
Explanation:
For the first test case, The answers will be true because :
Task 1 and task 2 can be assigned to server 1.
Task 3 can be assigned to server 2.
Task 4 and task 5 can be assigned to server 3.
In this way, we can schedule all the given tasks.

For the second test case, the answer will be false because we can not assign task 1 to any server.
Sample Input 2:
2
2 4
8 8
4 4 4 4
1 2
16 
8 12
Sample Output 2:
true
false
Hint

Try every possible combination.

Approaches (1)
Depth-First Search

In this approach, we will try every possible combination using DFS. For each task, we will try to assign it to each server. We will check if all tasks are scheduled, then we will return true. Otherwise, we will return false. 

 

Algorithm:

  • Create a function DFS(index, servers, tasks):
    • Initialize a variable result with a false value.
    • If the index is greater than or equal to tasks.size
      • return true
    • Iterate i in 0 to servers.size
      • If servers[i] - tasks[i] is greater than or equal to 0
        • servers[i] = servers[i] - tasks[i]
        • Set result as logical OR operation of result and dfs(index+1, servers, tasks)
        • servers[i] = servers[i] + tasks[i]
    • Finally, return result.
       
  • Set the answer as DFS(0, servers, tasks).
  • Return the variable answer.
Time Complexity

O(N ^ M), where N and M are the number of servers and tasks, respectively.
 

For each DFS call, we have N choices of servers, and there will be a total of M DFS calls. Hence the overall time complexity is O(N^M).

Space Complexity

O(M), where M is the number of tasks.

 

The recursion stack requires O(M) space in the worst case. Hence the overall space complexity is O(M).

Code Solution
(100% EXP penalty)
Servers And Tasks
Full screen
Console