スキャンラインアルゴリズム

問題をソートする方法の1つであるスキャンラインアルゴリズムを使用します.
問題を順番に処理されたイベントのセットとしてモデリングします.
主にO(n^2)の時間的複雑さが解決できないか,DPを用いて注釈を必要とするデータが大きすぎることが考えられる.
ソート後の処理ロジックは,O(Nlogn)の時間的複雑さを持つ.
例
BOJ 2170スクライブ
https://www.acmicpc.net/problem/2170
私の考え
重複線に違いはなく、座標位置を特定するだけです.
直線がどこから始まるかが重要なので、x座標を基準に並べ替えます.
その後、最初の0のleft,rightをxとy座標に置き、繰り返し繰り返し、次の座標のy座標が既存のleftより小さい場合は、つながっているやつだと思っています.
そうでなければ未接続の線分と判断し、接続の情報を計算した後、新しいx、y座標で線分を再開する.
コード#コード#

class BOJ2170 {
    fun solve(){
        val n = readLine()!!.toInt() // 선 그은 횟수 , 최대 1,000,000임
        val list = mutableListOf<Pair<Int,Int>>()

        var left = (-1e9).toInt()
        var right = (-1e9).toInt()
        var result = 0

        repeat(n){
            val (x,y) = readLine()!!.split(' ').map { it.toInt() }
            list.add(Pair(x,y))
        }

        list.sortBy { it.first }

        for(i in 0 until n){
            // 만약 , x좌표가 기존의 right보다 작다면 , 이는 합칠 수 있는 선분임
            if(list[i].first < right){
                right = max(right,list[i].second) // 합침
            } else { // 합칠 수 없는 선분이라면 , 혹은 반복문의 첫번째 단계라면
                result += (right - left) // 그 전까지의 선분들을 전부 계산하고
                left = list[i].first // 새로운 왼쪽과
                right = list[i].second // 새로운 오른쪽으로 갱신후 다시 작업을 진행한다
            }
        }

        result += right - left
        println(result)
    }
}

心得
GRADYアルゴリズムを行う過程では,ソート後に操作する必要がある場合があるが,ソートのさらなる学習が必要であると考える.
時間の複雑さにもっと注意しなければならないようだ.
これに関連する問題は容易ではありません...😂