Half and Half Flights

Medium

A company has two offices and is sending every employee to one of them for an on-site week, exactly half to each. For employee i, a ticket to the first office costs fares[i][0] and a ticket to the second costs fares[i][1]. Return the smallest total ticket cost that puts exactly half of the employees in each office.

Example 1

fares=[[40, 15], [25, 30], [60, 70], [12, 50]] → 117

Employees 2 and 3 fly to the first office (60 + 12), employees 0 and 1 to the second (15 + 30), for a total of 117: employee 1 pays only 5 extra for the second office, less than anyone else would.

Example 2

fares=[[5, 9], [3, 8]] → 12

Both would rather fly to the first office, but only one can go there. Sending employee 0 to the second office is cheaper: 9 + 3 = 12 versus 5 + 8 = 13.

Constraints

2 ≤ len(fares) ≤ 10⁴, and the length is even
1 ≤ fares[i][0], fares[i][1] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Biggest Number From Pieces Medium Studios for Recording Sessions Medium Low, High, Low Medium Strictly Low, High, Low Medium Fewest Meetings to Cancel Medium

Input

fares=[[40, 15], [25, 30], [60, 70], [12, 50]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.