[白俊]13334号:鉄道

7921 ワード
heap sweeping Sort kotlin テキストリンク
質問リンク
  • h<=oの条件がないので、始点と終点を統一するために、h<=oの条件を実施する.
  • 到着点を昇順に並べ替えます.
  • 0から(n-1).
    • 開始点を
  • の最小ヒップに入れ、peek値が(現在の到達点-d)値より小さい場合は、すべてポップアップします.
  • 最小臀部の寸法は、(現在の到達点−d)に含まれる鉄道の数を表す.
    • import java.util.*
import kotlin.math.max

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()

    val lines = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        var (h, o) = br.readLine().split(" ").map { it.toInt() }
        if (h > o) {
            val temp = h
            h = o
            o = temp
        }
        lines.add(Pair(h, o))
    }
    lines.sortBy { it.second }
    val d = br.readLine().toInt()

    var answer = 0
    val pq = PriorityQueue<Int>(compareBy { it })
    for (i in 0 until n) {
        pq.add(lines[i].first)
        while (pq.isNotEmpty() && pq.peek() < (lines[i].second - d)) pq.poll()
        answer = max(answer, pq.size)
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

    時間の複雑さ


    O(n * logn)
    Javaベース
    Gradle 2.4.1=>Gradle 4.1アップグレードログ