pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 686 (Div. 2) Medium. SegmentsAndPoints

問題概要

n 個の点と n 個の区間が与えられるので、区間とその区間に含まれる点をペアにする。n個すべてのペアを作ることはできるだろうか。

解法

点を昇順にソートして、左から順にペアにできる右端が最も小さい区間とペアにすればいい。

TopCoder SRM 686 (Div. 2) Medium. SegmentsAndPoint ...

制約が緩いから簡単に書ける。制約がきつくても走査すれば解ける。