javascript - 이 알고리즘을 구현하는 방법은 무엇입니까?

Question

데이터 형식은 다음과 같습니다.

으아악

요구사항 설명:
1일 좌표 지도(00:00 - 24:00)에 각 데이터를 플롯합니다.

가능한 다이어그램은 다음과 같습니다:

1. 데이터의 startTime和endTime에 따라 Y축의 데이터 좌표를 얻을 수 있습니다( 상단 및 높이 값으로 표현, 구현 )

2. 각 기간은 교차할 수 있으므로(한 이벤트의 기간(startTime - endTime)의 일부가 다른 이벤트의 기간에 속하므로 교차라고 함) X에서 교차하는 이벤트는 축이 균등하게 나누어집니다 의 너비 값이 클수록 위치가 가까워집니다X 轴上相交的事件平分X轴的宽度(表现为left和width值)
2.1.如果一个事件没有与任何事件相交，则这个事件的宽度是100%
2.2 如果相交平分的话，必须order2.3 이벤트는 다른 이벤트와 교차할 수도 있고, 여러 이벤트와 교차할 수도 있습니다

제 질문은 X축 너비를 이등분하고 왼쪽 위치를 지정하는 알고리즘을 구현하는 방법입니다. 즉, 각 요소의 왼쪽과 너비가 알고리즘의 가치가 있습니다

보충 내용: A와 B가 교차하고, B와 C가 교차하고, A와 C가 교차하지 않으면 ABC도 똑같이 나누어집니다

Answer 1

대략 작성하면 기본 아이디어는

1. 먼저 모든 작업을 큰 것부터 작은 것 순으로 정렬합니다(이 부분은 생략)

2. start end를 눌러 작업 개체를 생성하고, 그림 개체 중 add_one을 사용하여 차례로 그림에 추가합니다.

3. 객체 삽입 시 기존 객체 중 겹치는 객체를 확인하고, 그 왼쪽을 가장 큰 중첩 객체의 왼쪽+1과 동일하게 만들고 동시에 최대 너비를 업데이트합니다

4. 마지막으로 is_overlap 메서드를 사용하여 어떤 이벤트와도 교차하지 않는 작업에서 이벤트를 감지하고 표시합니다. 이러한 이벤트의 왼쪽은 0으로 설정되고, 이러한 이벤트 이외의 이벤트에 대해서는 너비가 100%로 설정됩니다. , 너비는 1/max_width로 설정, 왼쪽은 1/max_width*(left-1)으로 설정 (이 부분은 생략)

다음 코드는 2단계와 3단계입니다

으아악

Answer 2

2D 그룹화

• 첫 번째 수직 그룹(VGroups). 교차 관계가 있는 이벤트는 동일한 그룹으로 그룹화됩니다. 각 그룹은 독립적입니다(그룹이 교차하지 않음). 그룹화 알고리즘은 다음과 같습니다. 각 이벤트를 노드로 처리하고 두 노드가 교차하면 가장자리가 연결됩니다. 이렇게 해서 그래프가 얻어지고, 그룹화는 이 그래프의 연결된 구성요소를 찾는 것입니다. 깊이 우선 검색 또는 너비 우선 검색과 같은 알고리즘을 사용하여 연결된 구성 요소를 찾을 수 있습니다. VGroups）。凡之间有相交关系的事件分入同一组。各组之间是独立的（组间不相交）。分组算法是：将每个事件看做节点，若两个节点相交，则连一条边。这样得到一个图，分组即求此图的连通分量。可以用深度优先搜索或者广度优先搜索等算法求连通分量。

• 纵向组内再横向分组（HGroups

  수직 그룹(HGroups) 내에서 수평으로 그룹화합니다.
교차 관계가 없는 이벤트는 동일한 그룹으로 그룹화됩니다(그룹은 교차하지 않음). 이 단계의 목적은 나란히 표시할 수 있는 이벤트 수를 압축하고 빈 공간을 활용하는 것입니다.

이렇게 두 차원을 수직, 수평으로 그룹화한 후 그래픽으로 변환하는 것은 간단합니다.

테스트

첨부:

Mahematica🎜 코드🎜 으아악

Answer 3

@saigyouyou
이럴 수도 있겠네요