leetcode

0 class Solution {

1 public:

2 int twoCitySchedCost(vector<vector<int>> &costs) {

3 sort(begin(costs), end(costs),

4 [](const auto &a, const auto &b) { return (a[0] - a[1]) < (b[0] - b[1]); });

5 int n = costs.size() / 2, res = 0;

6 for (int i = 0; i < n; i++)

7 res += costs[i][0] + costs[i + n][1];

8 return res;

9 }

10 };

11

12 // Little optimization

13 class Solution {

14 public:

15 int twoCitySchedCost(vector<vector<int>> &costs) {

16 const int n = costs.size() / 2;

17 nth_element(begin(costs), begin(costs) + n, end(costs),

18 [](const auto &a, const auto &b) { return (a[0] - a[1]) < (b[0] - b[1]); });

19 int res = 0;

20 for (int i = 0; i < n; i++)

21 res += costs[i][0] + costs[i + n][1];

22 return res;

23 }

24 };