일정 예약과 이진 탐색 트리(BST)
2019. 4. 16. 01:48
본 내용은 Deep Into Algorithm from MIT 강의를 들으며 정리한 내용이다. 오늘 해결할 문제는 "활주로 예약 시스템"이다. 활주로 예약 시스템 활주로가 매우 혼잡하고 활주로는 단 하나뿐인 공항 향후 착륙을 위한 "예약" 필요 비행기가 착륙하면 대기 중인 사건 집합에서 제거 각각의 착륙 요청에는 "요청 예약 시간" t가 명시되어 있음 t로부터 k분 전이나 k분 후에 다른 착륙 예약이 없다면, t를 집합에 추가함. k값은 변할 수 있음 이 외의 경우에는 에러로 보고, 예약을 잡지 않는다. - 예시 R(착륙시간) = (41, 46, 49, 56) , k = 3, now = 37 이므로 t = 44 는 허용되지 않는다. (44+3을 하면 46이 겹친다.) t = 53 은 허용된다. t = 2..