[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 length is , so all the total choices will be , 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 first.
But how to sort it?
By what?
If we choose a person who has lower , but if his is more lower than another person’s , that means the total cost will be larger.
If let people all fly to city B, then choose people of them change to fly city A, the company need a extra cost .
Ahha, Eureka! We Got It!
Sort the array by , the fist person to city A, others go to city B.
Let’s coding.
1 | public static int twoCitySchedCost(int[][] costs) { |
In fact, we don’t need an extra array. We can optimize the code.
1 | public static int twoCitySchedCost_opt(int[][] costs) { |
Analysis
- Time Complexity: .
- Space Complexity: .
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. 😉😃💗