Job Assignment
1.0s 256MThere are \(N\) employees in your company, numbered from \(1\) to \(N\).
The company received two orders today, each of which must be completed by a single employee. Employee \(i\) requires time \(A_i\) to complete the first order and time \(B_i\) to complete the second.
The company wants to minimize the completion time of these two orders. If both orders are assigned to employee \(i\), the total time is \(A_i + B_i\); if they are assigned to employees \(i\) and \(j\) (with \(i \ne j\)), the completion time is \(\max(A_i, B_j)\).
Compute the minimum time required to complete both orders.
Input
The first line contains a positive integer \(N (2 ≤ N ≤ 1000)\), the number of employees.
Each of the next \(N\) lines contains two positive integers \(A_i, B_i (1 ≤ A_i, B_i ≤ 10^5)\), representing the time employee \(i\) requires to complete the first and second orders, respectively.
Output
Output a single integer: the minimum time required to complete both orders.
Sample Input 1
3
8 5
4 4
7 9
Sample Output 1
5
Sample Input 2
3
11 7
3 2
6 7
Sample Output 2
5
Sample Explanation
In the first sample test case, we can assign order \(1\) to employee \(2\) and order \(2\) to employee \(1\), so it takes only \(max(5, 4) = 5\) time to finish these two orders.
In the second sample test case, we can assign both orders to employee \(2\), so it takes only \(3 + 2 = 5\) time to finish these two orders.
Source
Log in to write and submit code. Creating an account is free.