구간 스케줄링이라는 장르의 문제인 것 같습니다. 공식 해설만으로는 슬프겠지만, 나에게는 이해할 수 없었기 때문에 그림에 써 이해해 보았습니다.

문제는 여기입니다.

입력 예

입력 예

4
2 4
4 3
9 3
100 5

그림

이렇게 그림에 그려 보면 "어째서 그런 일인가, 확실히 그렇다고 하네요"라는 느낌이 들었습니다.

1번째의 가장 오른쪽 가장자리와 2번째의 가장 왼쪽 끝을 비교해 가고, 2번째의 왼쪽 끝이 1번째의 오른쪽 끝보다 숫자가 작으면, 그 2번째를 제거해 나가면 좋을 뿐입니다.

코드

코드로 하면 이런 느낌.

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";

시간에 여유가 생기면 수시로 갱신하고 싶습니다.
코멘트 있으면, 꼭 잘 부탁드립니다!