BOJ 15337 - Starting a Scenic Railroad Service

BOJ 15337 - Starting a Scenic Railroad Service

1번의 정답은 어떤 한 구간에 대해서 그 구간 안에 포함되는 구간의 개수 중 최댓값을 구하는 문제이고

2번의 정답은 그냥 모든 구간에서 제일 많이 겹칠 때 얼마나 겹치는지 구하는 문제이다.

2번의 정답은 그냥 골드 스위핑 문제로 아무렇게나 구해줄 수 있다.

1번의 정답은 전체 구간의 개수에서 안겹치는 구간의 개수를 빼주는 것으로 할 수 있다.

$[L, R]$ 일 때, 구간이 $L$ 이하에서 끝나거나 $R$ 이상에서 시작하는 구간의 개수를 빼주면 된다.

이는 구간합 배열로 빠르게 구할 수 있다.