Assign 2n Workers to Two Tasks to Minimize Total Time
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You manage `2n` workers and two tasks, **A** and **B**. Every worker must be assigned to exactly one task, and each task must be staffed by **exactly `n` workers**.
Workers are not equally good at both tasks. Worker `i` needs `time[i][0]` hours to do their share if assigned to task A, and `time[i][1]` hours if assigned to task B.
Return the **minimum possible total number of hours worked**, summed over all `2n` workers, over all valid assignments.
## Examples
**Example 1**
```
Input: time = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
```
Assign workers 0 and 1 to task A (10 + 30 hours) and workers 2 and 3 to task B (50 + 20 hours). Total = 110. No other assignment with two workers per task does better.
**Example 2**
```
Input: time = [[5, 8], [2, 4]]
Output: 9
```
With n = 1, one worker goes to each task. Assigning worker 0 to task B and worker 1 to task A costs 8 + 2 = 10; assigning worker 0 to task A and worker 1 to task B costs 5 + 4 = 9. The minimum is 9.
**Example 3**
```
Input: time = [[7, 7], [3, 3], [1, 9], [9, 1]]
Output: 12
```
Workers 2 and either of {0, 1} go to task A, and worker 3 with the remaining one goes to task B: 1 + 3 + 1 + 7 = 12.
## Constraints
- `time.length == 2n` where `1 <= n <= 10^5`
- `1 <= time[i][0], time[i][1] <= 10^9`
- The answer fits in a signed 64-bit integer.
- An `O(n log n)` solution is expected; trying all assignments is far too slow.
## Output
Return the minimum total hours as an integer.
Quick Answer: This question evaluates algorithmic problem-solving skills in combinatorial optimization and resource allocation, focusing on reasoning about cost differences when assigning 2n workers into two equal-sized tasks and belongs to the Coding & Algorithms domain.
You manage `2n` workers and two tasks, **A** and **B**. Every worker must be assigned to exactly one task, and each task must be staffed by **exactly `n` workers**.
Worker `i` needs `time[i][0]` hours if assigned to task A, and `time[i][1]` hours if assigned to task B. Return the **minimum possible total number of hours worked**, summed over all `2n` workers, over all valid assignments.
**Example 1**
```
Input: time = [[10, 20], [30, 200], [400, 50], [30, 20]]
Output: 110
```
Assign workers 0 and 1 to task A (10 + 30) and workers 2 and 3 to task B (50 + 20). Total = 110.
**Example 2**
```
Input: time = [[5, 8], [2, 4]]
Output: 9
```
With n = 1, assign worker 0 to A (5) and worker 1 to B (4). Total = 9.
**Example 3**
```
Input: time = [[7, 7], [3, 3], [1, 9], [9, 1]]
Output: 12
```
Total = 1 + 3 + 1 + 7 = 12.
**Constraints**
- `time.length == 2n` where `1 <= n <= 10^5`
- `1 <= time[i][0], time[i][1] <= 10^9`
- The answer fits in a signed 64-bit integer.
- An `O(n log n)` solution is expected.
Constraints
- time.length == 2n where 1 <= n <= 10^5
- 1 <= time[i][0], time[i][1] <= 10^9
- The answer fits in a signed 64-bit integer.
- An O(n log n) solution is expected.
Examples
Input: [[10, 20], [30, 200], [400, 50], [30, 20]]
Expected Output: 110
Explanation: Workers 0,1 -> A (10+30), workers 2,3 -> B (50+20). Total 110.
Input: [[5, 8], [2, 4]]
Expected Output: 9
Explanation: n=1: worker 0 -> A (5), worker 1 -> B (4). Total 9.
Input: [[7, 7], [3, 3], [1, 9], [9, 1]]
Expected Output: 12
Explanation: Deltas 0,0,8,-8; move the two smallest (workers 3 and one of 0/1) to B. Total 12.
Input: [[1000000000, 1], [1, 1000000000]]
Expected Output: 2
Explanation: Send worker 0 to B (1) and worker 1 to A (1). Total 2 — exercises 64-bit range.
Input: [[5, 5], [5, 5]]
Expected Output: 10
Explanation: All deltas are 0; any split costs 10.
Input: [[1, 2], [3, 4], [5, 6], [7, 8], [9, 10], [11, 12]]
Expected Output: 39
Explanation: n=3, all deltas equal 1; sum of A-costs 36 plus three deltas of 1 = 39.
Hints
- Imagine first putting every worker on task A. The running cost is the sum of all `time[i][0]`. Now you must move exactly n of them to task B.
- Moving worker i from A to B changes the total by `time[i][1] - time[i][0]`. To minimize the total, move the n workers whose delta is smallest.
- Sort the 2n workers by `time[i][1] - time[i][0]` ascending; the first n go to B, the rest stay on A. This is O(n log n).