이벤트 겹침
실버 III의견: 0
공연 기획사 '리스엔터'에는 이벤트 \(N\)개가 예정되어 있다. 각 이벤트는 반개구간 \([s, e)\)에 진행된다. 즉 시각 \(s\) 이상 \(e\) 미만 동안 열린다.
두 이벤트 \(i\), \(j\)가 겹친다는 것은 \(s_j < e_i\) 이고 \(s_i < e_j\)인 경우를 말한다. (끝점이 맞닿기만 하고 공유 구간이 없으면 겹치지 않는다.)
각 이벤트 \(i\)에 대해, \(i\)와 겹치는 다른 이벤트의 수를 구하여라.
- \(1 \le N \le 100\,000\)
- \(0 \le s < e \le 10^9\)
- 이벤트는 반개구간 \([s, e)\)로 진행된다.
첫째 줄에 이벤트의 수 \(N\)이 주어진다.
다음 \(N\)개의 줄에 이벤트의 시작 시각 \(s\)와 종료 시각 \(e\)가 공백으로 구분되어 주어진다.
각 이벤트에 대해, 해당 이벤트와 겹치는 다른 이벤트의 수를 입력 순서대로 한 줄에 공백으로 구분해 출력한다.
4
1 5
3 7
6 9
10 15
1 2 1 0
이벤트 \([1,5)\)와 \([3,7)\)은 서로 겹친다 (겹침: \(3 < 5\) and \(1 < 7\)). \([1,5)\)는 \([3,7)\)과만 겹치므로 답 \(1\), \([3,7)\)는 \([1,5)\)와 \([6,9)\)와 겹치므로 답 \(2\), \([6,9)\)는 \([3,7)\)와만 겹치므로 답 \(1\), \([10,15)\)는 아무것도 겹치지 않아 답 \(0\)이다.
3
0 10
0 10
0 10
2 2 2
세 이벤트가 완전히 같은 구간이므로 각 이벤트는 나머지 \(2\)개와 모두 겹쳐 답은 \(2, 2, 2\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
이벤트 겹침
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
이벤트 겹침