Two City Scheduling

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
MicrosoftAmdocs

Problem statement

Ninja is planning to organize an exhibition in which ‘2N’ peoples are coming. The hall’s capacity in which the exhibition is going to take place is only ‘N’. So, ninja thinks of organizing two exhibitions in 2 different cities, ‘CITY_A’ and ‘CITY_B’, each of capacity ‘N’. All ‘2N’ people will come to the exhibition but in the group of ‘N’ in two different cities. Ninja wants your help in organizing this event.

You are given an array ‘COST’ where “COST[i] = [COST_TO_Ai, COST_TO_Bi]”, in which ‘COST_TO_Ai’ is the cost of the ith person to fly to the city A, and ‘COST_TO_Bi’ is the cost of the ith person to fly to the city B. Your task is to find the minimum cost of organizing the exhibition in which every person flies to a city such that exactly ‘N’ people arrive in each city.

Note:

The intersection of the set of the persons who go to ‘CITY_A’ to those going to ‘CITY_B’ is to be disjoint set, whereas the union must be the ‘2N’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the 'T' test cases follow. 

The first line of each test case contains a positive integer, ‘N’,  such that ‘2N’ is the number of people coming to the exhibition.

The next ‘2N’ lines of each test case contain two integers, ‘COST_TO_Ai’, and ‘COST_TO_Bi’, as described in the problem statement.
Note: 
The ‘COST’ will be passed to the function as an array of arrays. Each array will contain two integers, ‘COST_TO_Ai’, and ‘COST_TO_Bi’ in that order.
Output Format: 
For each test case, return the minimum cost of organizing the exhibition, as described in the problem statement.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 50
COST.length == 2*N
1 <= CostToAi, CostToBi <= 10^4

Time Limit: 1sec
Sample Input 1:
1
2
5 100
50 10
10 200
100 20
Sample Output 1:
45
Explanation for sample input 1:
The first person will go to City ‘A’ at the cost of 5.

The second person will go to City ‘B’ at the cost of 10.

The third person will go to City ‘A’ at the cost of 10.
The last person will go to City ‘B’ at the cost of 20.
So, the total minimum cost will be = 5 + 10 + 10 + 20 = 45. There is no other way to get the cost less than 45.
Sample Input 2:
1
1
200 200
100 200
Sample Output 2:
300
Explanation for sample input 2:
The first person will go to City ‘B’ at the cost of 200.

The second person will go to City ‘A’ at the cost of 100.
So, the total minimum cost will be = 200 + 100 = 300. There is no other way to get the cost less than 300.
Hint

Think of a recursive solution with memoization.

Approaches (2)
Dynamic Programming

The idea here is to use the recursion. For every ‘ith’ person, we have two options available. The first one is to fly to ‘City A’ for the cost of ‘COST_TO_Ai’, and the second is to fly to ‘City B’ for the cost of ‘COST_TO_Bi’. If at any point we have sent ‘N’ persons to one city, then we have to send the remaining peoples to the other city only. We have to always return the minimum in every function call. To avoid the function to again compute the result for the same function call, we can save the previously called function’s output that is nothing but the memoization.

 

 

Steps:

  • At each function call, we need three states that are current index, the count of the persons who have already gone to City A, and the count of the persons who have gone to City B.
  • So, we need a 3 states dynamic programming, i.e.,  MEMO[2*N+1][N+1][N+1], as described above. We can substitute ‘N’ to 50 here so; our ‘MEMO’ looks like MEMO[101][51][51].
  • Initialize 'MEMO' with -1.
  • Call the function SOLVE(INDEX, COUNTA, COUNTB, COST), where the index is the current of the array ‘COST’, 'COUNTA' is initially 0, 'COUNTB' is also initially 0, and the cost is the given array of arrays.
  • Return the return value of the above function.


 

int solve(int index, int countA, int countB, int cost[][]):

  • If 'INDEX' == ‘2N’ (which is cost.length), then simply return 0.
  • If MEMO[INDEX][COUNTA][COUNTB] != -1, return MEMO[INDEX][COUNTA][COUNTB].
  • If COUNTA == ‘N’ (which is COST.length / 2), then we have to send the ith person to ‘City B’, so return MEMO[INDEX][COUNTA][COUNTB] = COST[INDEX][1] + SOLVE(INDEX+1, COUNTA, COUNTB+1, COST).
  • Else If 'COUNTB' == ‘N’ (which is COST.length / 2), then we have to send the ith person to ‘City A’, so return MEMO[INDEX][COUNTA][COUNTB] = COST[INDEX][0] + SOLVE(INDEX+1, COUNTA+1, COUNTB, COST).
  • Else, we have to send the ith person to both the cities one by one, and return the minimum of them, i.e., return MEMO[INDEX][COUNTA][COUNTB] = min(COST[INDEX][0] + SOLVE(INDEX+1, COUNTA+1, COUNTB, COST), COST[INDEX][1] + SOLVE(INDEX+1, COUNTA, COUNTB+1, COST)).
Time Complexity

O(N^2), where ‘N’ is the number of peoples in each city.

 

There are 2 options available for every person to go to either City ‘A’ or City ‘B’. From this, you can say that it is a 2^N solution, but if you look carefully, we are using the memoization technique, which will reduce the time complexity to O(N^2).

Space Complexity

O(N^3), where ‘N’ is the number of peoples in each city.
 

As we are using the three states dynamic programming. So, the space complexity will be O(N^3).

Code Solution
(100% EXP penalty)
Two City Scheduling
Full screen
Console