이벤트를 시작 시각 순으로 보며, 이미 끝난 레인 중 가장 낮은 것에 넣고, 없으면 레인을 하나 늘린다. 이렇게 하면 레인 수가 동시에 겹치는 최대 개수와 같아진다(구간 그래프의 탐욕 색칠). 겹치는 것끼리 묶은 그룹마다 레인 수를 세어 너비를 100% ÷ 레인 수, 위치를 레인 ÷ 레인 수로 둔다. 예: A 9–11, B 10–12, C 11–13 이면 A·C 가 레인 0, B 가 레인 1 이고 레인은 둘이다. D 14–15 는 새 그룹이라 혼자 전체 폭이다.

-- 겹치는 이벤트를 나란히 놓는다: 시작 순으로, 비어 있는 가장 낮은 레인에
assign :: [Event] -> [(Event, Lane)]
assign = go [] . sortOn (\e -> (start e, end e))
  where
    go _     []       = []
    go lanes (e : es) = (e, l) : go (set l (end e) lanes) es
      where l = fromMaybe (length lanes) (findIndex (<= start e) lanes)   -- 끝난 레인 중 가장 낮은 것
-- 레인 수 = 동시에 겹치는 최대 개수 (구간 그래프의 탐욕 색칠) — 가능한 한 적은 레인으로 모두 덮는 최적해다

-- 겹치는 것끼리 그룹으로 묶어 그룹마다 total 을 센다
groups :: [Event] -> [[Event]]   -- 다음 시작 < 그룹의 최대 끝이면 같은 그룹
style (lane, total) = { left = lane / total * 100%, width = 100% / total }

assign [A 9 11, B 10 12, C 11 13] == [(A, 0), (B, 1), (C, 0)]   -- total 2

출처

`#510`