AtCoderのRobot armsの問題を絵に描いて理解してみる（PHP）

区間スケジューリングというジャンルの問題らしいです。公式の解説だけでは、悲しいかな、僕には理解できなかったので、絵に書いて理解してみました。

問題はこちらです。

入力例

入力例

4
2 4
4 3
9 3
100 5

絵

こうやって絵に描いてみると「なんだそんなことか、確かにそりゃそうだよね」って感じになりました。

１番目の一番右端と２番目の一番左端を比べていって、２番目の左端が１番目の右端よりも数字が小さければ、その２番目を取り除いていけばいいだけですね。

コード

コードにするとこんな感じ。

PHP

<?php
    fscanf(STDIN, "%d", $n);
    for ($i = 0; $i < $n; $i++) {
        fscanf(STDIN, "%d %d", $x, $l);
        $ss[] = max(0, $x - $l);
        $ts[] = $x + $l;
    }
    array_multisort($ts, SORT_ASC, $ss);
    $t = 0;
    $count = 0;

    for ($i = 0; $i < $n; $i++) {
        if ($ss[$i] >= $x) {
            $count++;
            $t = $ts[$i];
        }
    }
    echo $count . "\n";

時間に余裕ができたら随時更新していきたいです。
コメントあれば、ぜひよろしくお願い申し上げます！