そんな難しいか？
要素数が0なら終了
始点と終点を組みにして始点でソートして始点の小さい方から全部キューに入れる
キューから一つ取り出して変数tに入れる
while (キューが空でない) {
キューから一つ取り出す
取り出した始点がtの終点以下であればtの終点を大きい方に設定
そうでなければtを結果に加えtに取り出したデータを入れる
}
tを結果に加える
O(n)だろ