Last Updated: 19 Dec, 2020

Christmas Eve

Easy

Asked in companies

Solve now

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?

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

Solve now

Approaches

01 Approach

Note that:

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.
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’.

Solve now