paizaラーニング レベルアップ問題集 ソートメニュー応用編 JavaScript スケジューリング

スケジューリング (paizaランク B 相当)

解いてみました。

キャンペーンの参加数を最大化するには、
終了日が早い順にソートをすれば良いです。

あるキャンペーンが終わって、次のキャンペーンに参加する条件は、
あるのキャンペーンの終了日と次のキャンペーンの開始日を比較すれば良いです。

C++ の場合の模範解答を参考にJavaScriptでコードを書いてみました。

JavaScript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//キャンペーンは n 回開催
const n = Number(lines[0]);

//キャンペーン開始日・終了日の配列
let campaign = [];
for (let i = 1; i <= n; i++) {
    campaign.push(lines[i].split(" ").map(Number));
}
//キャンペーン終了日の早い順にソート
campaign.sort((a, b) => a[1] - b[1]);

let participated_campaigns = 0;//参加できるキャンペーン日数
let campaign_lastday = 0;//あるキャンペーンの終了日
for (let i = 0; i < n; i++) {
    //あるキャンペーンの終了日より、開始日が早ければ
    if (campaign_lastday < campaign[i][0]) {
      participated_campaigns++;//参加できる
      campaign_lastday = campaign[i][1];//終了日を更新
    }
}
console.log(participated_campaigns);

また、メソッドを使って、キャンペーン開始日・終了日の配列をソートするところを、まとめて以下のようにも書けます。

JavaScript

//キャンペーン開始日・終了日の配列
const campaign = lines.slice(1)
    .map(line => line.split(" ").map(Number))
    //キャンペーン終了日の早い順にソート
    .sort((a, b) => a[1] - b[1]);