psj1028   3년 전

처음에는 단순히 sorted를 사용하여  meetings를 x,y 순으로 오름차순으로 정렬하고, 

end_time을 target으로하여 binary search를 이용해서 적절한 다음 회의 start time을 찾아보려고 했습니다.

계속해서 해결이 되지 않아 질문 게시판을 찾아봤고,

정렬 시에 종료 시간을 기준으로 정렬을 해야하며, 종료 시간이 같을 시에 시작 시간 순으로 오름차순 정렬을 해야함을 알게 되었습니다.

이렇게 될 경우에 발생하는 문제점이.. binary search를 적용할 수 없다는 점인데요(start time이 섞이기 때문)

6
4 6
5 5
5 5
5 5
5 5
4 6

이런 케이스에서 문제가 발생함을 확인하였습니다.

binary search 대신 다른 방식을 생각해 봤는데,

정렬이 "잘" 되어 있으므로,

반복문을 돌면서 (end time < 다음 회의 start time)을 만족하는 경우 count를 하는 방식으로 하면 될 것이라고 생각합니다.

제가 정말로 궁금한 점은.

여기서 binary search를 적용하는 것은 불필요한 과정인지.. 만약에 굳이 사용하고 싶다! 하면 어떻게 적용하면 좋을지 의견 부탁드리겠습니다!

댓글을 작성하려면 로그인해야 합니다.