Skip to content
This repository has been archived by the owner on Nov 19, 2019. It is now read-only.

How about using greedy algorithm for stacking? #20

Open
vlsi opened this issue Jul 20, 2018 · 0 comments · May be fixed by #26
Open

How about using greedy algorithm for stacking? #20

vlsi opened this issue Jul 20, 2018 · 0 comments · May be fixed by #26
Labels
perf improvment

Comments

@vlsi
Copy link

vlsi commented Jul 20, 2018

https://en.wikipedia.org/wiki/Interval_scheduling#Greedy_polynomial_solution

Current stack.stack is O(N^2): https://github.com/yotamberk/timeline-plus/blob/master/lib/timeline/Stack.js#L57-L70

It looks like the following O(N log N) algorithm should produce sane outputs:

  1. Order by finish time
  2. Try to fit items, and stack up those that overlap
@saharki saharki linked a pull request Jul 28, 2018 that will close this issue
Open
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
perf improvment
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Stack with time complexity of O(N logN) saharki/timeline-plus
2 participants
@vlsi @yotamberk