다른 정수 모양의 직사각형을 둘러싸는 직사각형 공간을 최소화하려는 경우 백 트랙킹을 피할 수 있습니까?

Question

내 문제의 추상화는 직교 좌표계에서 많은 직사각형이 있다는 것입니다. 이 사각형은 알려진 정수 크기를 가지며 정수 좌표를 가져야합니다. 가로 좌표 (가로 좌표)는 알려져 있고 고정되어 있으며 세로 좌표 만 다를 수 있습니다.

문제는 지정된 모든 사각형을 포함하는 가장 작은 사각형이 최소 인 좌표를 찾는 것입니다. 이는 작은 직사각형이 가로로 고정되어 있기 때문에 폭이 고정되어 있기 때문에 최소 높이를 가져야 함을 의미합니다.

백 트랙킹을 사용해야하는지 또는 더 빠른 방법이 필요한지 모르겠지만 50 개의 직사각형을 사용하면 올바른 솔루션을 계산할 때 측정 가능한 시간이 걸리고 욕심 많은 알고리즘이 나와 잘 어울리지 않는다고 상상할 수 있습니다. .

편집 : 죄송합니다. 지금은 충분히 명확하지 않습니다. 내가 처음이 질문을했을 때 나는 달력 응용 프로그램을 작성하고있었습니다. 관리자가 팀의 이벤트를 작성합니다.

• 이벤트 A는 오후 2 시부 터 시작합니다. 오후 4시에 끝납니다.
• 이벤트 B는 오후 5시에서 시작합니다. 오후 6시에 끝납니다.
• 이벤트 C는 오후 4시에서 시작합니다. 오후 6시에 끝납니다.
• 이벤트 D는 오후 2 시부 터 시작합니다. 오후 3시에 끝납니다.
• 이벤트 E는 오후 3 시부 터 시작합니다. 오후 5시에 끝납니다.

타임 라인에 이러한 이벤트를 표시하고 싶습니다. 관리자가 가능한 한 작은 화면 공간을 차지하지 않도록하고 싶습니다 (관리자가 각 이벤트를 사각형으로보고 싶고 그 설명을보고 싶어하기 때문에). 구형).

가

+-----+-----+ 
| A | C | 
+---+-+-+---+ 
| D | E | B | 
+---+---+---+ 

A와 C는 라인이며, D, E, B가 서로 같습니다

예에 대한 최상의 구성은 다음 상술 될 것이다. 욕심 많은 접근 방식은 A와 B를 같은 줄에, C와 D를 다른 줄에, E를 세 번째 줄에 놓았습니다.

Answer 1

질문을 올바르게 읽으면 주어진 사각형 세트를 다루는 최소 사각형을 찾아야합니다. 맞습니까?

입력 조건에 따라 가로 좌표 범위가 고정되므로 세로 좌표 범위 만 찾아야합니까?

그렇다면 '최소 바닥'과 '최대 상단'에 대해 주어진 사각형 세트를 스캔하면 원하는 사각형이 정의됩니다.

Answer 2

이벤트의 시간 순서를 유지합니다. 달력을 작성 중이므로 연대기 순서가 완벽합니다. 먼저 시작되는 이벤트를 보여줍니다.

저는 스크린 부동산 문제를 다르게 해결할 것이고, 요소를 재 포장하지 않을 것입니다. 예를 들어 요소 크기를 줄이면 사용자가 요소 위로 마우스를 가져 가면 더 많은 정보가 포함 된 도구 설명이 표시됩니다. 사용자가 마우스 클릭으로 요소를 선택하면 완전한 정보를 표시합니다.