this is for holding javascript data
Xavier Holt added Line_Segments_Algorithm_and_Runtime__.md
about 8 years ago
Commit id: ea52d555bf66bf68074db46444f03d79728345e0
deletions | additions
diff --git a/Line_Segments_Algorithm_and_Runtime__.md b/Line_Segments_Algorithm_and_Runtime__.md
new file mode 100644
index 0000000..b61f982
--- /dev/null
+++ b/Line_Segments_Algorithm_and_Runtime__.md
...
# Line Segments
## Algorithm and Runtime
- `H` \(\Leftarrow\) Heap
- For segment `i` by ascending x-coordinate: O(n)
- Pop `h` from `H` until `i` can hit `h` or `H` is empty: RTP amortised O(1).
- Emit index of `h` or 0 in the empty `H` case: O(1).
- Push `h` followed by `i` onto `H`: O(1).
