Leetcode - 1029. Two City Scheduling

1.質問

💡 A company is planning to interview  2n  people. Given the array  costs  where  costs[i] = [aCosti, bCosti] , the cost of flying the  ith  person to city  a  is  aCosti , and the cost of flying the  ith  person to city  b  is  bCosti .
Return the minimum cost to fly every person to a city such that exactly  n  people arrive in each city.

2n取材者が必要で、1人A都市・B都市への所要料金(料金)は順次支給される.

全員をそれぞれの都市に送るための最低料金を探し出す.

4人なら2人でA都市へ、2人でB都市へ.

2 <= costs.length <= 100

costs.length  is even.

2.誤った第一の方法

まず、コストの長さが100なので、すべての場合の数字をBrute Forceで求めて解くことは可能でしょうか?という考えが生まれた.与えられた費用の手配の中で、A都市を巡視する時、B都市に分けた時、すべての状況を観察する.

しかし、このような状況の欠点は明らかだ.すべての場合、答えは正確ですが、時間の複雑さはO(2 n 2^n 2 n)で、配列の長さが100なら...?1.26765002282294e+30.数字を読むのも難しくなります.

3.第2の方法

では、両都市に行く費用の違いで、各都市に行く費用の重み付け値を見ることができますか?近づいてきました.costs = [[10,20],[30,200],[400,50],[30,20]]時B도시 비용 - A도시 비용の値を求めると[10, 170, -350, -10]この値は、値が大きいほどB都市への相対費用が大きくなり、値が小さいほどB都市への相対費用が小さくなることを意味する.
次のように昇順で並べ替えます.

値段が小さいほど、A都市よりB都市のほうがいいです.B都市料金とA都市料金の差を基準に選んだので、絶対料金に差があっても総料金は最小料金となります.
この場合の全時間複雑度はO(nlognlognlogn)である.各差異を求め、すべてのコストを求めるのはO(n)であり、昇順ソートにはO(nlognlogn)が必要である.上記のBrute Forceに比べて時間的複雑さが大幅に減少した.

4.正解コード

function twoCitySchedCost(costs) {
  return costs
    .map(cost => cost.concat(cost[1] - cost[0]))
    .sort((a, b) => a[2] - b[2])
    .reduce((acc, cur, i) => {
      if (i < costs.length / 2) {
        return acc + cur[1];
      } else {
        return acc + cur[0];
      }
    }, 0);
};

高次関数をフィルタリングし、順番に

mapで各エレメントを巡回し、B도시 비용 - A도시 비용値をエレメントに追加します.

各要素の追加B도시 비용 - A도시 비용料金の差異を基準に昇順で並べ替えます.

半分はA市、半分はB市に送るのでindexに準ずるcosts.length / 2B市より小さく、A市より大きい料金を加算する.

意味する.