Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Ресторан
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Ресторан $n$ ширхэг түрээсийн захиалга авчээ. Түрээс бүр тодорхой тасралтгүй хугацаанд үргэлжлэх ба $i$-дэх захиалга нь $l_{i}$ хугацаанд эхлэн $r_{i}$ хугацаанд дуусна ($l_{i} ≤ r_{i}$).
Ресторан захиалгыг зөвшөөрч эсвэл зөвшөөрөхгүй байж болно. Тэгвэл ресторан хамгийн олондоо хэчнээн захиалгыг зөвшөөрч чадах вэ?
Аль ч хоёр зөвшөөрөгдсөн захиалгын үргэлжлэх хугацаа нь хормын төдийд ч огтлолцож болохгүй. Ямар нэгэн агшинд нэг захиалга нь дуусчихсан, нөгөө захиалга нь эхэлж байвал уг хоёр захиалга хоёул зөвшөөрөгдөж болно.
Оролт
Эхний мөрөнд захиалгын тоо болох $n$ ($1 ≤ n ≤ 5*10^{5}$) байна. Дараагийн $n$ мөрөнд $l_{i}$ ба $r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$) тоонууд байна.
Гаралт
Зөвшөөрч болох захиалгуудын хамгийн их утгыг хэвлэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
2 7 11 4 7
Гаралт
1
Оролт
5 1 2 2 3 3 4 4 5 5 6
Гаралт
3
Оролт
6 4 8 1 5 4 7 2 5 1 3 6 8
Гаралт
2