Data Stream as Disjoint Intervals – Fishercoder

Data Stream as Disjoint Intervals – Fishercoder

I'm thinking to maintain the numbers as a sorted array, but it doesn't give me quick insertion into the correct place

Then I was thinking to use the previous problem Insert Interval to help with this one, but that's purely cheating and I'm not if that can work either.

The moment, I clicked the Tag, it shows Binary Search Tree, I'm impressed!

• It's this thought process that values! Don't click to show Tags too early, think about it, which data structure would you come up to use?

Now, my thoughts:

• try to use the idea from https://fishercoder.com/2016/07/16/count-of-smaller-numbers-after-self/
• to build a BST, while inserting a new node, check to see if merge is needed, check both the node's parent and child, let each node's value be the lower boundary of the interval and define another field which is the array of interval in this node class
• after trial and error, rewriting it multiple times: discussion with badyu2000@ here: https://discuss.leetcode.com/topic/47084/java-fast-log-n-solution-186ms-without-using-the-treemap-but-a-customized-bst/12
• I've got my 100% original code to pass 8/9 test cases, I'm really excited about it, my thought process could be visited in that thread, but I'm still puzzled why the last case didn't pass, from my eyes check, I don't see any difference between my output and the expected output.

Read full article from Data Stream as Disjoint Intervals – Fishercoder