https://codeforces.com/contest/1297/problem/B

1297b_editorial.md

https://codeforces.com/contest/1297/problem/B

区間の重なりを O(C+T) で解く方法として、 いもす法 が知られているが、この問題では T が 10^9 に達するため、いもす法では解くことが出来ない。

この問題で数えるべき「区間の重なりの数が1」の区間は、区間の端っことその前後に属する区間の数を数えることで、O(C^2) で数えることができる。

本番ではいもす法では解けないことを理解していたので、区間を重ねてみて冷静に観察すれば解けた... はずである(´ー｀; )

fun oneInRange(arr: ArrayList<Pair<Int, Int>>, pos: Int): Boolean {
    var cnt = 0
    val n = arr.size
    for (l in 0..n-1) {
        val c = arr[l]
        if (c.first <= pos && pos <= c.second) {
            cnt++
        }
     }
     if (cnt == 1) {
        return true
     }
     return false
}

fun main(args: Array<String>) {
    val t = readLine()!!.toInt()

    for (i in 1..t) {
        val n = readLine()!!.toInt()
        var arr = ArrayList<Pair<Int, Int>>()
        for (j in 1..n) {
            val (a, b) = readLine()!!.split(" ").map { it.toInt() }
            arr.add(Pair(a, b))
        }

        var ans = -1
        for (k in 0..n-1) {
            val cur = arr[k]
            val from = cur.first
            val prevfrom = cur.first - 1
            val to = cur.second
            val toNext = cur.second + 1

            if (oneInRange(arr, from)) {
                ans = from
                break
            }
            if (oneInRange(arr, prevfrom)) {
                ans = prevfrom
                break
            }
            if (oneInRange(arr, to)) {
                ans = to
                break
            }
            if (oneInRange(arr, toNext)) {
                ans = toNext
                break
            }
        }
        println(ans)
    }
}