Timeline for Merging algorithm for overlapping intervals
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 27, 2019 at 16:14 | vote | accept | Sazzad Hissain Khan | ||
| Jun 21, 2017 at 8:33 | comment | added | Bart van Ingen Schenau | @SazzadHissainKhan: With an array or list, finding the insertion point (and check for merge) is still O(log(n)). Making room to insert a new element, or filling a gap created by merging is O(n). If the comparison takes about as many instructions as moving an element, then the overall complexity is O(n). | |
| Jun 20, 2017 at 21:09 | comment | added | Sazzad Hissain Khan | Its only possible using BST as u suggested, not with array or linked list i guess. I mean O(log(n)). | |
| Jun 20, 2017 at 21:04 | comment | added | Telastyn | @SazzadHissainKhan - no, you don't. You keep things in order, insert ordered, and it's around O(ln(n)) | |
| Jun 20, 2017 at 20:48 | comment | added | Sazzad Hissain Khan | Dynamic array matters because for each insert and update I have to do the whole process (the referenced algorithm) which leads into a O(n^2) complexity. I want an efficient algorithm. | |
| Jun 20, 2017 at 18:19 | history | answered | Telastyn | CC BY-SA 3.0 |