Last Updated: 11 Dec, 2020
Minimum days to complete work
Easy
Asked in companies
We have to complete a total of ‘N’ works. Now, each work can be done on only one of the two special days given in 2 different arrays ‘day1’ and ‘day2’ respectively.
day1[i] denotes that the ‘i-th’ work can on the day1[i] th day and day2[i] denotes that the ‘i-th’ work can on the day2[i] th day. Also, it is guaranteed that day2[i] < day1[i].
Also, make sure, the works are being done in such a way that they must be in non-decreasing order in terms of days given in array ‘day1’.
Your task is to find the minimum number of days in which all the work can be completed.
For example
day1 = {5, 6, 2}
day2 = {2, 4, 1}
In this case, the ideal order will be to perform work 3 on the first day, work 1 on the second day and work 2 on the fourth day. The order with respect to Day1 in which the work is done will be {2, 5, 6} which is non-decreasing. Hence the number of days needed to finish all work will be 4.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘3 * T’ lines represent the ‘T’ test cases.
The First line of each test case contains a single integer ‘N’ denoting the number of works to be done.
The second line contains ‘N’ space-separated integers denoting the sequence day1.
The last line contains ‘N’ space-separated integers denoting the sequence day2.
Output format :
For each test case, return the minimum number of days required to complete the work.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints:
1 <= T <= 50
0 <= N <= 10^3
1<= day1[i],day2[i] <= 10^9
Time Limit: 1 sec
Approaches
- Since it is guaranteed that day2[i] < day1[i] and also we need to ensure that the order in which the work is done is non decreasing in terms of day1[i], we can pair up each work and sort the pairs in terms of increasing order of day1[i].
- If we do the works in this way we can guarantee that we will finish the works as soon as possible and also ensuring the order of work done is non-decreasing with respect to day1.
- Now, let ‘combined’ be the array in which combined[i].first = Day1[i] and combined[i].second = Day2[i]
- First, we complete the work on combined[1].second in the sorted order and Move to the second work. If we can complete it on day combined[2].second such that (combined[1].second <= combined2[2].first), we do the second work
- Otherwise, do the work on day day2[2]. Repeat the process until we complete the N-th work, keeping the day of the latest work.
We can take the Following Approach:
- Make an array of pairs named ‘combined’ and pair up day1[i] and day2[i].
- Sort the ‘combined’ array in terms of the increasing value of day1[i].
- Initialize a variable ‘ans’ to the least value possible(-1 in this case)
- Then iterate through the ‘combined’ array and first check if combined[i].second is greater than answer then make answer equal to combined[i].second
- Otherwise, update the answer to combined[i].first it is guaranteed that ‘ans <= combined[i].first’ because we sorted the array in increasing order of combined[i].first
- Finally, return the value of ‘ans’