Last Updated: 6 Apr, 2021
Two City Scheduling
Moderate
Asked in companies
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’.
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
Approaches
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)).
The idea here is to use the greedy approach. First, we send all persons to ‘CITY_A’ and calculate the total cost of doing so. Now, we want ‘N’ persons to go to ‘CITY_B’ from ‘CITY_ A’ so that our total cost would be minimal. So, if we send the ith person from ‘CITY_A’ to 'CITY_B', we have to subtract ‘COST_TO_A’ and add ‘COST_TO_B’. In other words, we have to calculate the value of “COST_TO_Bi - COST_TO_Bi” for all ‘i’, and store it into a new array. After that, we have to sort the array in the non-decreasing order and just send the starting ‘N’ persons to ‘CITY_B’.
Steps:
- Create a new array of size ‘2N’ named ‘SEND_A_TO_B’.
- Create a variable named 'TOTAL_COST', and initialize it to 0.
- Run a loop from ‘i’ = 0 to ‘i’ < 2*'N', in each iteration do:
- Add COST[i][0] to the 'TOTAL_COST'.
- Add element “COST[i][1] - COST[i][0]” into the array ‘SEND_A_TO_B’.
- Sort the array 'SEND_A_TO_B' in non-decreasing order.
- Now, run a loop from ‘i’ = 0 to ‘i’ < ‘N’, in each iteration do:
- Add SEND_A_TO_B[i] into the totalCost.
- Return the 'TOTAL_COST'.
Similar problems