1029. Two City Scheduling
Previous874. Walking Robot SimulationNext1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Last updated
Was this helpful?
Last updated
Was this helpful?
use greedy
因為透過觀察,
cost[0] - cost[1] 的話, 會是 -10, -170, 350, 10
代表越小的結果, 應該派去 A, 會最好,
本題說要一半的人去 A 一半的去 B, 所以透過排序 cost[0] - cost[1] , 由小到大
前一半的人去 A, 後一半的人去 B , 會是最佳解!
O(nlogn), O(1)
dp 解
dp[i][j]
represents the cost when considering first (i + j)
people in which i
people assigned to city A and j
people assigned to city B.
O(n^2), O(n^2), N = costs.length / 2