By Long Luo

Let’s use it by brute force way.

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