[일반] 이거 문제 어케 풀어야함??

[익명(220.118)]

2차원 배열로 입력받아서 오름차순으로 소팅하는거 까진했는데 그다음에 어떻게 풀어야할지 모르겠음..

[0xrgb(0xrgb)]

소팅하고 하나씩 빼보는걸 시뮬레이션 할텐데 그냥 하면 너무 느리니까 스캐닝을 할거임

[0xrgb(0xrgb)]

먼저 자명한 경우를 생각해봐야하는데, 어떤 사람의 일하는 시간이 다른 사람의 일하는 시간에 완전 포함되면 시간 손해 없이 뺄 수 있음

[0xrgb(0xrgb)]

그걸 제외한 경우는 내 앞의 시간대중에서 가장 늦게 끝나는 시간 - 내 뒤의 시간대에서 가장 빠르게 시작하는 시간을 계산하고 내가 빠지면 얼마나 구멍이 생기는지 계산하면 됨

[0xrgb(0xrgb)]

그러면 소팅이 O(n lg n)이고 스캐닝이 O(N) 이라서 무난하게 나올거임

[0xrgb(0xrgb)]

그런데 어디문제임? 예전 USACO에서 비슷한거 본거 같은데

[익명(220.118)]

만약 0번째변 어뜨케해??

[0xrgb(0xrgb)]

내 앞의 시간대중 가장 늦게 끝나는 시간을 -Inf로 생각하면 될듯. 마찬가지로 맨 뒤도