Starting a Scenic Railroad Service

• 문제를 잘 해석하고 조금 생각해보면 요구사항이 정리된다. policy-1 은 구간들 중에서 그 구간과 겹치는 구간의 갯수가 가장 많은 구간을 찾으라는 문제이다. 이때의 겹치는 구간의 갯수가 s1이 된다.. policy-2는 겹치는 구간의 갯수가 가장 많은 시점을 찾으라는 문제이다. 이때의 겹치는 구간의 갯수가 s2이다.
• s2는 자주 나오는 흔한 문제이다. 탑승시간과 하차시간을 모두 모아서 정렬한다음, 빠른시간부터 스위핑하면서 현재 겹치는 구간의 수를 업데이트해주면 된다. 탑승시간이면 +1, 하차시간이면 -1을 해주면서 유지하고, 이 과정에서 나온 최댓값이 답이다.
• s1은.. 세그먼트 트리를 써도 풀수 있긴 하고, 태그에도 그렇게 달려있긴 한데.. 그냥 스위핑을 해서 O(n)에 풀수 있다. 어떤 구간 [xl,xr]에 대해서 [yl, yr]이 겹치기 위해서는, x에서 하차하기 전에 y에 탑승해야 하고 (yl<xr), x에서 탑승하기 전에 이미 y에서 하차했으면 안된다 (yr>xl). 이 조건을 만족하는 y의 갯수를 찾는 것은, 탑승 이벤트의 누적합과 하차 이벤트의 누적합을 유지해주면 계산 가능하다. x의 탑승 시점에서, 여태까지의 하차 이벤트의 갯수를 빼주고, x의 하차시점에 여태까지의 탑승 이벤트의 갯수를 더해주면, x와 겹치는 구간의 갯수가 된다. 이렇게 모든 x에 대해서 겹치는 구간의 수를 계산해준다음, 최댓값을 찾으면 s1이 된다.
  • 풀고나서 알게된 다른 풀이는, 전체에서 안겹치는 구간의 갯수를 빼주는 것이다. 안겹치는 구간은 하차시간이 x의 탑승시간보다 빠르거나, 탑승시간이 x의 하차시간보다 느린 구간이다. 구현해놓으면 비슷하지만 개념적으로 이해하기 좀더 깔끔한 느낌.?
• 시간 복잡도는 O(n). 위의 두가지 스위핑은 간단하게 한번에 구현할수 있다.

"""Solution code for "BOJ 15337. Starting a Scenic Railroad Service".

- Problem link: https://www.acmicpc.net/problem/15337
- Solution link: http://www.teferi.net/ps/problems/boj/15337

Tags: [Sweeping]
"""

import sys

ALIGHTING, BOARDING = 0, 1


def main():
    n = int(sys.stdin.readline())
    events = []
    for i in range(n):
        a, b = [int(x) for x in sys.stdin.readline().split()]
        events.append((a, BOARDING, i))
        events.append((b, ALIGHTING, i))

    events.sort()
    s2 = 0
    overlapping_section_count = [0] * n
    boarding_count = alighting_count = 0
    for _, type_, i in events:
        if type_ == BOARDING:
            boarding_count += 1
            overlapping_section_count[i] = -alighting_count
            s2 = max(s2, boarding_count - alighting_count)
        else:
            alighting_count += 1
            overlapping_section_count[i] += boarding_count
    s1 = max(overlapping_section_count)

    print(s1, s2)


if __name__ == '__main__':
    main()