Условие

Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер a_i и до сектора b_i включительно, и устанавливал на него очередную систему. При этом, если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.

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

Примеры

Ввод: 10 3 1 3 4 7 3 4 Вывод: 1

Ввод: 10 4 1 3 4 5 7 8 4 6 Вывод: 3

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max
import kotlin.math.min

// Класс для представления раздела диска
data class Partition(val start: Long, val end: Long)

// Функция для проверки пересечения двух разделов
fun overlaps(p1: Partition, p2: Partition): Boolean {
    // Пересечение есть, если начало одного интервала меньше или равно концу другого,
    // и наоборот. Более простой способ: максимальное из начал <= минимальному из концов.
    return max(p1.start, p2.start) <= min(p1.end, p2.end)
}

fun main(args: Array<String>) {
    // Используем BufferedReader для быстрого чтения
    val reader = BufferedReader(InputStreamReader(System.`in`))
    // Используем BufferedWriter для быстрого вывода
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Читаем M (количество секторов), оно не используется в логике, но есть во вводе
    val m = reader.readLine().toLong()
    // Читаем N (количество создаваемых разделов)
    val n = reader.readLine().toInt()

    // Список для хранения активных (не затертых) разделов
    val activePartitions = mutableListOf<Partition>()

    // Обрабатываем каждый создаваемый раздел
    for (i in 0 until n) {
        // Читаем начальный и конечный секторы нового раздела
        val parts = reader.readLine().split(" ")
        val currentStart = parts[0].toLong()
        val currentEnd = parts[1].toLong()
        val newPartition = Partition(currentStart, currentEnd)

        // Список для хранения разделов, которые останутся активными ПОСЛЕ добавления нового
        val partitionsToKeep = mutableListOf<Partition>()

        // Проверяем пересечение нового раздела со всеми ранее созданными активными разделами
        for (existingPartition in activePartitions) {
            // Если существующий раздел НЕ пересекается с новым, он остается активным
            if (!overlaps(existingPartition, newPartition)) {
                partitionsToKeep.add(existingPartition)
            }
            // Если пересекается, то существующий раздел "затирается" и не добавляется в partitionsToKeep
        }

        // Обновляем список активных разделов (теперь он содержит только те, что не были затерты)
        activePartitions.clear()
        activePartitions.addAll(partitionsToKeep)

        // Добавляем новый раздел в список активных
        activePartitions.add(newPartition)
    }

    // Выводим количество активных разделов
    writer.write(activePartitions.size.toString())

    // Закрываем потоки ввода-вывода
    reader.close()
    writer.close()
}