1029. Two City Scheduling

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int ret = 0, n = costs.size()/2;
        vector<int> refund;
        for(auto & cost:costs){
            ret+=cost[0];
            refund.push_back(cost[1] - cost[0]);
        }
        sort(refund.begin(), refund.end());
        for(int i=0;i<n;++i) ret+=refund[i];
        return ret;
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity O(n)