Christmas Eve

Easy
0/40
Average time to solve is 15m
profile
Contributed by
15 upvotes
Asked in companies
AmazonBarclays

Problem statement

Radhika is preparing for Christmas Eve. She decided that there would be ‘N’ different dishes on the dinner table, numbered from 1 to N. Since Radhika doesn't like to cook, she wants to order these dishes from restaurants.

Unfortunately, all dishes are prepared in different restaurants and therefore Radhika needs to pick up her orders from N different places. To speed up this process, she wants to order courier delivery at some restaurants. Thus, for each dish, there are two options for Radhika how she can get it:

1) The dish will be delivered by a courier from the restaurant ‘i’, in this case, the courier will arrive in A[i] minutes,

2) Radhika goes to the restaurant ‘i’ on her own and picks up the dish, she will spend B[i] minutes on this.

Each restaurant has its own couriers and they start delivering the order at the moment Radhika leaves the house. In other words, all couriers work in parallel. Radhika must visit all restaurants in which she has not chosen delivery, she does this consistently.

Thus, you are given an integer ‘N’ denoting the number of dishes Radhika wishes to order and two integer arrays ‘A’ and ‘B’ of size ‘N’ where A[i] is the time required to deliver dish ‘i’ and B[i] is the time required to pick up the dish ‘i’. As Radhika is very busy, can you help her by finding the minimum time after which all the dishes can be at Radhika's home?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases. Then the test cases follow.

The first line of each test case contains an integer ‘N’ denoting the number of dishes that Radhika wants to order.   

The second line of each test case contains ‘N’ space separated integers denoting the elements of array ‘A’. 

The second line of each test case contains ‘N’ space separated integers denoting the elements of array ‘B’.
Output Format 
For each test case output an integer denoting the minimum time after which all dishes can be at Radhika’s home.

The output of each test case is printed in a separate line.
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 <= 10^4
1 <= A[i] <= 500
1 <= B[i] <= 500

Where A[i] is the time of courier delivery of the dish with the number, and B[i] is the time during which Radhika will pick up the dish with the number.

Time Limit: 1 sec
Sample Input 1:
1
4
3 7 4 5
2 1 2 4
Sample Output 1:
5

Explanation for Sample Input 1:

Radhika can order delivery from the first and the fourth restaurant, and go to the second and third on her own. 

Then the courier of the first restaurant will bring the order in 3 minutes, the courier of the fourth restaurant will bring the order in 5 minutes, and Radhika will pick up the remaining dishes in 1 + 2 = 3 minutes. 

Thus, in 5 minutes all the dishes will be at Radhika’s house.
Sample Input 2:
2
4
1 2 3 4
3 3 3 3
2
1 2
10 10

Sample Output 2:

3
2
Hint

Try to use the fact that all couriers work in parallel and independent time is required to pick up the dishes.

Approaches (1)
Sorting

Note that: 

  1. If we order a courier with time ‘X’, then all couriers with time less than ‘X’ can also be ordered, since all couriers work in parallel.
  2. The dishes that Radhika has to pick up requires independent time. 
     

Therefore, we can find the minimum time after which all dishes can be at Radhika’s home by keeping track of the sum of pickup times till it's less than the delivery time. If, at any moment, delivery time is more than the sum of the pick up times, just return the maximum of delivery time and sum of pick up times. This is because, remaining dishes can be ordered at the same time as couriers work in parallel. 
 

Algorithm: 

  • Create an array of pairs ‘tempArray’ of size ‘N’.
  • Store the elements of both the given arrays ‘A’ and ‘B’ such that the first element in the pair belongs to array ‘A’ and the second element belongs to array ‘B’.
    • For any index ‘i’, tempArray[i] = { A[i], B[i] }.
  • Now sort the ‘tempArray’ in descending order, according to the first element in the pairs.
  • Initialise an integer variable ‘ans’ with 0.
  • Traverse the ‘tempArray’:
    • If tempArray[i].second + ‘ans’ is less than tempArray[i].first, update ‘ans’ as ‘ans’ = ‘ans’ + tempArray[i].second.
    • Else, ‘ans’ will be the maximum of ‘ans’ and tempArray[i].first and break the loop since all the remaining dishes can be ordered and no extra time is required.
  • Return the ‘ans’.
Time Complexity

O(N * log(N), where N is the number of elements in the given arrays. 

 

We are sorting an array of size ‘N’ which takes O(N * log(N)) time. Also, we are traversing the array, which takes O(N) time in the worst case. Thus, the final time complexity is O(N * log(N) + N) = O(N * log(N)).

Space Complexity

O(N), where N is the number of elements in the given arrays. 

 

We are using an extra array of size O(N).Thus, the final space complexity is O(N). 

Code Solution
(100% EXP penalty)
Christmas Eve
Full screen
Console