# Minimum number of days required to complete the work

Given N works numbered from 1 to N. Given two arrays, D1[] and D2[] of N elements each. Also, each work number W(i) is assigned days, D1[i] and D2[i] (*Such that, D2[i] < D1[i]*) either of which can be completed.

Also, it is mentioned that each work has to be completed according to the **non-decreasing date of the array D1[]**.

The task is to find the **minimum number of days** required to complete the work in non-decreasing order of days in D1[].

**Examples**:

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input :

N = 3

D1[] = {5, 3, 4}

D2[] = {2, 1, 2}Output :2Explanation:

3 works are to be completed. The first value on Line(i) is D1(i) and the second value is D2(i) where D2(i) < D1(i). The smart worker can finish the second work on Day 1 and then both third work and first work in Day 2, thus maintaining the non-decreasing order of D1[], [3 4 5].

Input :

N = 6

D1[] = {3, 3, 4, 4, 5, 5}

D2[] = {1, 2, 1, 2, 4, 4}Output :4

### Recommended: Please try your approach on __{IDE}__ first, before moving on to the solution.

__{IDE}__**Approach:** The solution is greedy. The work(i) can be sorted by increasing D1[i], breaking the ties by increasing D2[i]. If we consider the works in this order, we can try to finish the works as early as possible. First of all complete the first work on D2[1]. Move to the second work. If we can complete it on day D2[2] such that (D2[1]<=D2[2]), do it. Otherwise, do the work on day D[2]. Repeat the process until we complete the N-th work, keeping the day of the latest work.

Below is the implementation of the above approach.

## C++

`// C++ program to find the minimum` `// number days required` `#include <bits/stdc++.h>` `using` `namespace` `std;` `#define inf INT_MAX` `// Function to find the minimum` `// number days required` `int` `minimumDays(` `int` `N, ` `int` `D1[], ` `int` `D2[])` `{` ` ` `// initialising ans to least value possible` ` ` `int` `ans = -inf;` ` ` `// vector to store the pair of D1(i) and D2(i)` ` ` `vector<pair<` `int` `, ` `int` `> > vect;` ` ` `for` `(` `int` `i = 0; i < N; i++)` ` ` `vect.push_back(make_pair(D1[i], D2[i]));` ` ` ` ` `// sort by first i.e D(i)` ` ` `sort(vect.begin(), vect.end());` ` ` `// Calculate the minimum possible days` ` ` `for` `(` `int` `i = 0; i < N; i++) {` ` ` `if` `(vect[i].second >= ans)` ` ` `ans = vect[i].second;` ` ` `else` ` ` `ans = vect[i].first;` ` ` `}` ` ` `// return the answer` ` ` `return` `ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `// Number of works` ` ` `int` `N = 3;` ` ` ` ` `// D1[i]` ` ` `int` `D1[] = { 6, 5, 4 };` ` ` ` ` `// D2[i]` ` ` `int` `D2[] = { 1, 2, 3 };` ` ` `cout<<minimumDays(N, D1, D2);` ` ` ` ` `return` `0;` `}` |

## Java

`// Java program to find the minimum` `// number days required` `import` `java.util.*;` `import` `java.lang.*;` `import` `java.io.*;` `// pair class for number of days` `class` `Pair` `{` ` ` `int` `x, y;` ` ` ` ` `Pair(` `int` `a, ` `int` `b)` ` ` `{` ` ` `this` `.x = a;` ` ` `this` `.y = b;` ` ` `}` `}` `class` `GFG` `{` `static` `int` `inf = Integer.MIN_VALUE;` `// Function to find the minimum` `// number days required` `public` `static` `int` `minimumDays(` `int` `N, ` `int` `D1[],` ` ` `int` `D2[])` `{` ` ` `// initialising ans to` ` ` `// least value possible` ` ` `int` `ans = -inf;` ` ` ` ` `ArrayList<Pair>` ` ` `list = ` `new` `ArrayList<Pair>();` ` ` ` ` `for` `(` `int` `i = ` `0` `; i < N; i++)` ` ` `list.add(` `new` `Pair(D1[i], D2[i]));` ` ` ` ` `// sort by first i.e D(i)` ` ` `Collections.sort(list, ` `new` `Comparator<Pair>()` ` ` `{` ` ` `@Override` ` ` `public` `int` `compare(Pair p1, Pair p2)` ` ` `{` ` ` `return` `p1.x - p2.x;` ` ` `}` ` ` `});` ` ` `// Calculate the minimum possible days` `for` `(` `int` `i = ` `0` `; i < N; i++)` `{` ` ` `if` `(list.get(i).y >= ans)` ` ` `ans = list.get(i).y;` ` ` `else` ` ` `ans = list.get(i).x;` `}` `return` `ans;` `}` `// Driver Code` `public` `static` `void` `main (String[] args)` `{` ` ` `// Number of works` ` ` `int` `N = ` `3` `;` ` ` `// D1[i]` ` ` `int` `D1[] = ` `new` `int` `[]{` `6` `, ` `5` `, ` `4` `};` ` ` ` ` `// D2[i]` ` ` `int` `D2[] = ` `new` `int` `[]{` `1` `, ` `2` `, ` `3` `};` ` ` ` ` `System.out.print(minimumDays(N, D1, D2));` `}` `}` `// This code is contributed by Kirti_Mangal` |

## Javascript

`<script>` ` ` `// Javascript program to find the minimum` `// number days required` `// Function to find the minimum` `// number days required` `function` `minimumDays(N, D1, D2)` `{` ` ` `// initialising ans to least value possible` ` ` `var` `ans = -1000000000;` ` ` `// vector to store the pair of D1(i) and D2(i)` ` ` `var` `vect = [];` ` ` `for` `(` `var` `i = 0; i < N; i++)` ` ` `vect.push([D1[i], D2[i]]);` ` ` ` ` `// sort by first i.e D(i)` ` ` `vect.sort((a,b)=>a-b)` ` ` `// Calculate the minimum possible days` ` ` `for` `(` `var` `i = 0; i < N; i++) {` ` ` `if` `(vect[i][1] >= ans)` ` ` `ans = vect[i][1];` ` ` `else` ` ` `ans = vect[i][0];` ` ` `}` ` ` `// return the answer` ` ` `return` `ans;` `}` `// Driver Code` `// Number of works` `var` `N = 3;` `// D1[i]` `var` `D1 = [6, 5, 4 ];` `// D2[i]` `var` `D2 = [1, 2, 3 ];` `document.write( minimumDays(N, D1, D2));` `</script>` |

**Output:**

6