By Long Luo

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