javascript - 求這個演算法如何實現?

Question

資料格式如下：

[
  {
    "event": {
      "id": "2013",
      "startTime": "00:57:00",
      "endTime": "07:56:00",
      "title": "list 1",
      "backgroundColor": "#f6c79f",
      "textColor": "#8c725b",
      "order": 2014
    }
  },
  {
    "event": {
      "id": "2016",
      "startTime": "00:51:59",
      "endTime": "06:57:00",
      "title": "list 2",
      "backgroundColor": "#a7bff7",
      "textColor": "#5f6d8c",
      "order": 2017
    }
  },
  {
    "event": {
      "id": "2019",
      "startTime": "00:11:00",
      "endTime": "11:35:00",
      "title": "list 3",
      "backgroundColor": "#beea91",
      "textColor": "#728c57",
      "order": 2020
    }
  },
  {
    "event": {
      "id": "2022",
      "startTime": "09:01:00",
      "endTime": "13:18:00",
      "title": "list 4",
      "backgroundColor": "#d1b1ff",
      "textColor": "#73618c",
      "order": 2023
    }
  }
]

需求描述：
在1天的座標地圖上(00:00 - 24:00)，繪製每個數據，

可能得示意圖如下：

1.根據資料的startTime和endTime可以求資料在Y 軸上的座標（表現為top以及height值，已實作）

2.由於每個時間段都可能相交（一個事件的時間段(startTime - endTime)的一部分在另一個一個事件的時間段中，叫做相交），則在X 軸上相交的事件平分X軸的寬度(表現為left和width值)
2.1.如果一個事件沒有與任何事件相交，則這個事件的寬度是100%
2.2 如果相交平分的話，必須order越大，位置越靠前
2.3 一個事件可能和另一個事件相交，也可能和另外幾個事件相交

我的問題是如何實現X軸平分寬度且定位left的演算法？也就是每個元素的left和width值得演算法

補充內容：A與B相交，B與C相交，A與C不相交，則ABC也是平分

Answer 1

大致寫了一下，基本思路是

1. 先將全部task依order從大到小排序(此部分省略)

2. 按start end產生task對象， 使用figure對象的add_one，依序加入figure。

3. 插入一個對象時，判斷已有對像中與其相重疊的對象，使其left為最大的重疊對象的left+1，同時更新最大width

4. 最後使用is_overlap方法檢測tasks中的沒有與任何事件相交的事件，並標記出來，這些事件left設為0，width設為100%，除了這些事件以外的事件，寬度設為1/max_width, left設為1/max_width*(left-1） （這部省略）

以下代碼為2和3的步驟

function task(start, end) {
    var _this = this;
    this.start = start;
    this.end = end;
    this.left = 0;
    this.width = 0;
    this.is_overlap = function (t1, t2) {
        return !((t1 < _this.start && t2 < _this.start ) || (t1 > _this.end && t2 > _this.end));
    }
}

function figure() {
    var _this = this;
    this.tasks = [];
    this.max_width = 0;
    this.add_one = function (obj) {
        var overlap = [];
        var max_left = 0;
        for(var i = 0; i < _this.tasks.length; i++) {
            if (_this.tasks[i].is_overlap(obj.start, obj.end)){
                overlap.push(_this.tasks[i]);
            }
        }
        for(var i = 0; i < overlap.length; i++) {
            max_left = Math.max(overlap[i].left, max_left);
        }
        obj.left = max_left + 1;
        _this.max_width = Math.max(obj.left, _this.max_width);
        _this.tasks.push(obj);
    }
}

var fig = new figure();
var tasks = [];
tasks[0] = new task(3, 10);
tasks[1] = new task(8, 14);
tasks[2] = new task(5, 12);
tasks[3] = new task(2, 9);
tasks[4] = new task(18, 21);
// tasks[0] = new task(9, 15);
// tasks[1] = new task(0, 22);
// tasks[2] = new task(3, 7);
// tasks[3] = new task(9, 15);

for (var i = 0; i< tasks.length; i++){
    fig.add_one(tasks[i]);
}

for (var i = 0; i< fig.tasks.length; i++){
    console.log('index: '+ i +'  left: ' + fig.tasks[i].left);
}
console.log('width :'+fig.max_width);

Answer 2

二維分組

• 先縱向分組（VGroups）。凡之間有相交關係的事件分入同一組。各組之間是獨立的（組間不相交）。分組演算法是：將每個事件看做節點，若兩個節點相交，則連一邊。這樣得到一個圖，分組即求此圖的連通分量。可以用深度優先搜尋或廣度優先搜尋等演算法求連通分量。

• 縱向組內再橫向分組（HGroups）。凡之間沒有相交關係的事件分入同一組（組內不相交）。這一步的作用是壓縮可以並列顯示的事件數，利用沒有佔用的空間。

這樣在縱橫兩個維度分組後，再轉換成圖形就是直截了當了。

測驗

附：Mahematica 代碼

renderEvents[evts_List] := 
 Map[SortBy[-#duration &] /* renderVGroup]@
  ConnectedComponents@
   RelationGraph[{e1, e2} \[Function] 
     IntervalIntersection[e1["duration"], e2["duration"]] =!= 
      Interval[], evts]

renderVGroup[evts_List] := Module[{hgs, n},
  hgs = Last@
    NestWhile[{Rest@First@#, 
       addToGroups[Last@#, First@First@#]} &, {evts, {}}, 
     First[#] != {} &];
  n = Length[hgs];
  MapIndexed[renderHGroup[#1, (First[#2] - 1)/n, 1/n] &]@hgs]

addToGroups[gs_List, e_] := Module[{p},
  p = FirstPosition[gs,
    g_ /; 
     IntervalIntersection[IntervalUnion @@ (#duration & /@ g), 
       e["duration"]] === Interval[],
    Missing["NotFound"], {1}, Heads -> False];
  If[Head[p] === Missing,
   Append[gs, {e}],
   ReplacePart[gs, First[p] -> Append[gs[[First[p]]], e]]]]

renderHGroup[evts_List, x_, w_] :=
 Map[{#["color"], 
    Rectangle[{x, Min[#["duration"]]}, {x + w, Max[#["duration"]]}], 
    Black, Text[
     Style[#["title"], 
      Medium], {x + w/2, (Max[#["duration"]] + Min[#["duration"]])/
       2}]} &, evts]

testEvents[n_] := Module[{events},
  events = 
   Table[<|"title" -> ToString[i], 
     "duration" -> Interval[{#, # + #2}] &[RandomReal[{0, 21}], 
      RandomReal[{1, 3}]], "color" -> Hue[i/n, 0.4], 
     "order" -> i|>, {i, n}];
  Graphics[{EdgeForm[Thin], renderEvents[events]}, AspectRatio -> 1, 
   GridLines -> {None, Range[24]}, 
   GridLinesStyle -> {LightGray, Dashed}, Axes -> {None, True}]]

Answer 3

@saigyouyou
有可能是這樣的