Minimum days to complete work

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

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
9 4 6
2 1 2
4
6 3 8 7
2 1 5 4
Sample Output 1 :
2
5
Explanation For Sample Input 1:
For the first test case:

We need two days for the above example.

If we do the first and third works first and then the second work then the order in which work is done according to Day1 will be: 6,9,4 which we can clearly see we will violate the conditions. As the order according to Day 1 is not non-decreasing because 9 comes after 4 which is violating the non-decreasing order condition.

However, On the first day, we do the second work and on the third day, we do the first and last works.
Hence we need two days to complete the work.



For the second test case:

We need two days for the above example.

We do the second work on the first day then the first work on the second day then the fourth work on the fourth day then the third work on the fifth day. The order in which work is done according to day1 will be 3,6,8,7 which is non decreasing which satisfies the conditions.
Sample Input 2 :
1
6
3 3 4 5 6 6
1 2 1 2 1 2
Sample Output 2 :
6
Hint

Try to sort the array and find the answer greedily.

Approaches (1)
Greedy Approach
  • 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’
Time Complexity

O(N * log(N)), Where ‘N’ denotes the number of works to be done

 

Since sorting the array takes the order of N * log(N), hence the overall complexity is O(N * log(N)).

Space Complexity

O(N), Where ‘N’ denotes the number of works to be done

 

Since we make an array of pairs which will have utmost ‘N’ elements the space complexity is the order of ‘N’.

Code Solution
(100% EXP penalty)
Minimum days to complete work
Full screen
Console