[Leetcode][1029. Two City Scheduling] Greedy: The Key is Sorting the Array by What?

By Long Luo

This article is the solution of Problem 1029. Two City Scheduling.

Let’s use it by brute force way.

The array 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 first.

But how to sort it?

By what?

If we choose a person who has lower cost_A, but if his cost_B is more lower than another person’s cost_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 cost_A - cost_B.

Ahha, Eureka! We Got It!

Sort the array by cost_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. 😉😃💗