캘린더 이벤트 배너를 효율적으로 레이아웃에 대한 알고리즘을 찾고 있습니다
https://stackoverflow.com/questions/400288
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Outlook 또는 Google Calendar의 Month View와 마찬가지로 하루 종일/멀티 며칠 이벤트 배너를 효율적으로 배치 할 수있는 알고리즘을 찾고 있습니다. 시작 및 종료 날짜가있는 여러 이벤트가 있으며, 시작 (및 종료) 날짜를 늘려서 주문합니다 (또는 다른 주문이 제기하는 경우 데이터베이스 테이블에서 이벤트를 수집하고 있습니다). 이벤트 배너 후에는 그 날을 위해 다른 이벤트를 배치해야하기 때문에 사용한 수직 공간의 평균 양을 최소화하고 싶습니다 (이것은 항상 주어진 날짜에 배너를 따라 온다). 예를 들어, 1/10-1/11과 1/11-1/15의 두 가지 이벤트가 있다면, 그렇게하는 것을 선호합니다 (각 열은 하루입니다).
bbbbb
aa
그리고 마음에 들지 않는다 :
aa
bbbbb
하루 (x, y 및 z)를 위해 이벤트를 추가 할 때, 나는 이것을 할 수 있기 때문입니다 (첫 번째를 선호하고 두 번째를 원하지 않습니다).
bbbbb vs. aa
aa xyz bbbbb
xyz
그러나 1/10-1/11, 1/13-1/14 및 1/11-1/13의 경우 더 긴 이벤트를 먼저 배치하는 것만 큼 간단하지 않습니다.
aa cc
bbb
반대로 :
bbb
aa cc
이벤트 X와 Y가 허용되기 때문입니다.
aa cc vs. bbb
xbbby aa cc
x y
물론 나는 이것을 한 번의 패스로 선호합니다. 데이터 구조의 경우 현재 날짜부터 목록까지지도를 사용하고 있는데, 여기서 매일 이벤트를 해당 목록에 추가합니다. 따라서 3 일간의 이벤트가 3 개의 목록에 나타납니다. 각 이벤트는 각각지도에서 하루 중 하나 아래에 있습니다. 이것은 결과를 시각적 출력으로 변환하기위한 편리한 구조이지만 다른 데이터 구조에도 열려 있습니다. 나는 현재 욕심 많은 알고리즘을 사용하고 있는데, 여기서 각 이벤트를 순서대로 추가하지만 다음과 같은 원치 않는 아티팩트를 생성 할 수 있습니다.
aa ccc
bbbbb
dd
eeeeeeeeeeeeeeeee
이것은 낭비 a 많은 대부분의 "E"이벤트 일을위한 공간.
어떤 아이디어?
해결책
다음은 하나의 가능한 솔루션의 높은 수준의 스케치입니다 (완전한 날짜 대신 주일 정수 사용). 이 인터페이스 :
public interface IEvent {
public abstract int getFirst(); // first day of event
public abstract int getLast(); // last day of event
public abstract int getLength(); // total number of days
public abstract char getLabel(); // one-char identifier
// true if this and that have NO days in common
public abstract boolean isCompatible(IEvent that);
// true if this is is compatible with all events
public abstract boolean isCompatibleWith(Collection<IEvent> events);
}
표현 된 알고리즘을 사용하려면 구현해야합니다. layout 아래 방법.
또한 콘크리트 클래스는 구현해야합니다 Comparable 더 긴 이벤트가 더 짧은 이벤트보다 우선하는 자연 순서를 만듭니다. (아래 데모의 샘플 구현은 하강 길이의 순서를 사용한 다음 시작 날짜를 올린 다음 오름차순 레이블을 사용했습니다.)
그만큼 layout 메소드는 수집을 취합니다 IEvent 인스턴스와 반환 a Map 프레젠테이션에서 각 행에 해당 행에 표시 될 수있는 이벤트 세트를 할당합니다.
public Map<Integer,Set<IEvent>> layout(Collection<IEvent> events) {
Set<IEvent> remainingEvents = new TreeSet<IEvent>(events);
Map<Integer,Set<IEvent>> result = new TreeMap<Integer,Set<IEvent>>();
int day = 0;
while (0 < remainingEvents.size()) {
Set<IEvent> dayEvents = new TreeSet<IEvent>();
for(IEvent e : remainingEvents) {
if (e.isCompatibleWith(dayEvents)) {
dayEvents.add(e);
}
}
remainingEvents.removeAll(dayEvents);
result.put(day, dayEvents);
++day;
}
return result;
}
각 행은 가장 긴 남은 이벤트를 선택하고 현재 행에 이전에 선택한 이벤트와 호환되는 모든 추가 이벤트 (위의 순서로)를 점차적으로 선택하여 구성됩니다. 그 효과는 모든 이벤트가 충돌없이 가능한 한 더 위로 "플로트"한다는 것입니다.
다음 데모는 무작위로 만들어진 이벤트 세트와 함께 두 가지 시나리오를 보여줍니다.
Event collection:
x(1):4
b(5):2..6
y(1):5
a(2):1..2
z(1):6
Result of layout:
0 -> {b(5):2..6}
1 -> {a(2):1..2, x(1):4, y(1):5, z(1):6}
Visual presentation:
bbbbb
aa xyz
Event collection:
x(1):1
b(3):2..4
a(2):1..2
c(2):4..5
y(1):5
Result of layout:
0 -> {b(3):2..4, x(1):1, y(1):5}
1 -> {a(2):1..2, c(2):4..5}
Visual presentation:
xbbby
aa cc
Event collection:
f(2):1..2
h(2):1..2
d(4):1..4
e(4):2..5
c(1):6
a(2):5..6
g(4):2..5
b(2):0..1
Result of layout:
0 -> {d(4):1..4, a(2):5..6}
1 -> {e(4):2..5, b(2):0..1, c(1):6}
2 -> {g(4):2..5}
3 -> {f(2):1..2}
4 -> {h(2):1..2}
Visual presentation:
ddddaa
bbeeeec
gggg
ff
hh
다른 팁
이런 상황에서 데이터가 먼저 올바르게 구성되어 있는지 확인한 다음 렌더링하는 것이 훨씬 좋습니다. 나는 당신이 단일 패스를 원한다는 것을 알고 있지만 결과가 더 나을 것이라고 생각합니다.
예를 들어, 주어진 날에 필요한 라인으로 데이터를 구성하고 가장 긴 이벤트부터 시작하여 가능한 가장 좋은 방법으로 이벤트를 구성하십시오 (먼저 표시 할 필요는 없지만 구성해야합니다. 먼저) 가장 짧은 이벤트로 내려갑니다. 이렇게하면 공간을 낭비하지 않고 "E"이벤트 일을 피할 수 있습니다. 또한 다음과 같이 :
bbb
aa cc
또는
aa cc
bbb
때문에 중요하지 않습니다 x 그리고 y 항상 양쪽에 갈 수 있습니다 bbb 또는 사이에도 aa 그리고 cc
도움이되기를 바랍니다.
