[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 $\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.

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.

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. 😉😃💗