[LeetCode][1029. Two City Scheduling] Greedy: Sorting the Costs Array by What?

By Long Luo

This article is the solution Greedy: Sorting the Costs Array by What? of Problem 1029. Two City Scheduling.

Intuition

Let’s use it by Brute Force way.

The array costs\textit{costs} length is nn, so all the total choices will be 2n2^n, that’s a really huge number, so we must find a better way!

Greedy

Obiviously, it’s solved by greedy.

We need to sort the array costs\textit{costs} first.

But how to sort it?

By what?

If we choose a person who has lower costAcost_A, but if his costBcost_B is more lower than another person’s costBcost_B, that means the total cost will be larger.

If let 2×n2 \times n people all fly to city B, then choose nn people of them change to fly city A, the company need a extra cost costAcostBcost_A - cost_B.

Ahha, Eureka! We Got It!

Sort the array by costAcostBcost_A - cost_B, the fist nn person to city A, others go to city B.

Let’s coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int twoCitySchedCost(int[][] costs) {
int len = costs.length;
int[][] diff = new int[len][2];
for (int i = 0; i < len; i++) {
diff[i][0] = i;
diff[i][1] = costs[i][0] - costs[i][1];
}

Arrays.sort(diff, (o1, o2) -> {
if (o1[1] == o2[1]) {
return o1[0] - o2[0];
}
return o1[1] - o2[1];
});

int ans = 0;
for (int i = 0; i < len / 2; i++) {
ans += costs[diff[i][0]][0];
}

for (int i = len / 2; i < len; i++) {
ans += costs[diff[i][0]][1];
}

return ans;
}

In fact, we don’t need an extra array. We can optimize the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int twoCitySchedCost_opt(int[][] costs) {
Arrays.sort(costs, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o1[1] - (o2[0] - o2[1]);
}
});

int len = costs.length;
int n = len / 2;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += costs[i][0] + costs[i + n][1];
}

return sum;
}

Analysis

  • Time Complexity: O(nlogn)O(nlogn).
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below .
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗