Условие

Новый Президент Тридевятой республики начал свою деятельность с полной ревизии системы общественного транспорта страны. В результате на основе социологических опросов населения было составлено идеальное ежедневное расписание движения междугородних автобусов, утверждённое Парламентом республики.

Более того, было решено заменить весь автобусный парк одинаковыми новыми, очень дорогими, но гораздо более надёжными, красивыми и удобными машинами.

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе F_i в момент времени X_i и заканчивается в некотором другом городе G_i в момент времени Y_i. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени X_i в городе F_i.

Новые автобусы не требуют ремонта и могут работать круглосуточно, поэтому автобус, прибывший в некоторый момент времени в некоторый город, всегда готов в тот же самый момент времени или позже отправиться в путь для обслуживания любого другого рейса из данного города. Автобус может выехать из города, только выполняя какой-либо рейс из расписания.

Предполагается, что расписание будет действовать неограниченное время, поэтому может оказаться так, что его невозможно обслужить никаким конечным числом автобусов.

Определите наименьшее количество новых автобусов, достаточное для обеспечения движения по расписанию в течение неограниченного периода времени.

Примеры

Ввод: 2 2 2 20:00 1 10:00 1 08:00 2 21:00 Вывод: 3

Ввод: 2 2 1 09:00 2 20:00 2 20:00 1 09:00 Вывод: 1

Ввод: 3 4 3 03:52 1 08:50 1 18:28 3 21:53 2 03:58 3 09:00 3 14:59 2 21:13 Вывод: 2

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.Comparator

data class Event(val time: Int, val city: Int, val type: Int)

fun parseTime(timeStr: String): Int {
    val parts = timeStr.split(":")
    val hours = parts[0].toInt()
    val minutes = parts[1].toInt()
    return hours * 60 + minutes
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val firstLine = reader.readLine().split(" ")
    val n = firstLine[0].toInt()
    val m = firstLine[1].toInt()

    val dailyBalance = IntArray(n + 1) { 0 }
    var midnightCrossings = 0L
    val events = mutableListOf<Event>()

    for (i in 0 until m) {
        val line = reader.readLine().split(" ")
        val f = line[0].toInt()
        val xStr = line[1]
        val g = line[2].toInt()
        val yStr = line[3]

        val xMinutes = parseTime(xStr)
        val yMinutes = parseTime(yStr)

        dailyBalance[f]--
        dailyBalance[g]++

        if (yMinutes < xMinutes) {
            midnightCrossings++
        }

        events.add(Event(xMinutes, f, -1))
        events.add(Event(yMinutes, g, +1))
    }

    for (city in 1..n) {
        if (dailyBalance[city] != 0) {
            writer.write("-1\\n")
            writer.flush()
            return
        }
    }

    val eventComparator = Comparator<Event> { e1, e2 ->
        if (e1.time != e2.time) {
            e1.time.compareTo(e2.time)
        } else {
            e2.type.compareTo(e1.type)
        }
    }
    events.sortWith(eventComparator)

    val currentBuses = IntArray(n + 1) { 0 }
    val minNeeded = IntArray(n + 1) { 0 }
    var totalInitialNeeded = 0L

    for (event in events) {
        val city = event.city
        val type = event.type

        if (type == 1) {
            currentBuses[city]++
        } else {
            currentBuses[city]--
            if (currentBuses[city] < 0) {
                minNeeded[city]++
                currentBuses[city] = 0
            }
        }
    }

    for (neededCount in minNeeded) {
        totalInitialNeeded += neededCount.toLong()
    }

    val result = totalInitialNeeded + midnightCrossings
    writer.write("$result\\n")
    writer.flush()
}