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.

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

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