시간표 이벤트 포장

Question

나는 학교 시간표로 일하고 있습니다. 시간 순서의 이벤트 목록을 수신하며 목표는 타임 라인에 표시하는 것입니다. 문제는 일부 이벤트가 다른 이벤트와 겹치는 것입니다 (아래 그림 참조). 내가하고 싶은 것은 가능한 한 가장 작은 공간에이 사건들을 "포장"하는 것입니다. This is single day with overlapping events.

첫 번째 그림은 지금까지 내가 관리했던 것을 보여줍니다. 그림에서 알 수 있듯이 직사각형은 서로 교차하지 않고 자유 공간을 멋지게 채 웁니다. 하지만 주문하기에 알맞은 알고리즘을 찾지 못했습니다. Second picture shows how events should be ordered.

이 고전 포장 문제에서이 문제를 다른 만드는 두 가지 조건을 다음과 같습니다

1. 이벤트 (시작과 끝으로 정의) x 좌표 부여하고있다.
2. 이벤트의 너비는 고정되어 있으며 높이는 임의입니다.

Answer 1

이 문제는 약간의 파일 시스템 조각화 문제를 상기시켜줍니다. 쉬운 해결책은 유명한 알고리즘 중 하나를 구현하는 것입니다. 처음 적합하거나 가장 적합하다.

하지만 최상의 솔루션을 원합니다. 그래서 backtracking algorithm을 구현하는 것이 좋습니다. 긴 런타임이 발생할 수 있지만이 문제는 사용자 환경에 별 문제가되지 않는다고 생각합니다.