백준 22867 - 종점

각 버스가 들어오고 나가는 것은 항상 짝이 맞습니다.

접근의 용이성을 위해 들어오는 것을 왼쪽 괄호 (, 나가는 것을 오른쪽 괄호 )로 생각하겠습니다.

사건의 시각이 주어져 있으므로 시간축을 가로축으로 하여 각 시각에 맞게 괄호를 늘어놓을 수 있습니다.

그러면 괄호가 가장 많이 겹쳐진 구간이 버스가 가장 많이 몰린 시간대이고 이때 겹쳐진 횟수가 답입니다.

괄호를 시간축에 늘어놓는 행위는 버스가 들어오고 나가는 사건을 시간순으로 정렬하는 것과 같습니다.

따라서 버스가 들어오고 나가는 사건을 시간순으로 정렬하고, 맨 처음 사건부터 버스가 들어오거나 나감에 따라 1을 각각 더하고 빼 주면 됩니다.

전체 사건의 개수는 $2N$개이므로 사건을 정렳하는 데 $O\left(N\log N\right)$, 시간대가 겹쳐진 횟수를 구하는 데 $O\left(N\right)$으로 전체 시간복잡도는 $O\left(N\log N\right)$입니다.

노트

버스가 종점에서 출발하는 것이 들어오는 것보다 우선임에 주의해서 정렬 순서를 정해야 합니다.

// event: (time, is_coming)
fn solve(events: &mut [(u32, bool)]) -> u32 {
    events.sort_unstable();
    let mut max_bus = 0;
    let mut bus = 0;
    for (_, is_coming) in events {
        if *is_coming {
            bus += 1;
            max_bus = std::cmp::max(max_bus, bus);
        } else {
            bus -= 1;
        }
    }
    max_bus
}