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 \(\textit{costs}\) length is \(n\), so all the total choices will be \(2^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 \(\textit{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 \times n\) people all fly to city B, then choose \(n\) 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 \(n\) 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)\).
• Space Complexity: \(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. 😉😃💗