Java | Object Oriented | TreeSet using ceiling and floor | O(n log n) for each insert
This question uses components of https://leetcode.com/problems/insert-interval/.\nHowever there is one difference. "Insert Interval" asks us to insert only one 
This question uses components of https://leetcode.com/problems/insert-interval/.\nHowever there is one difference. "Insert Interval" asks us to insert only one element. So I used a stack, and inserted. And it worked. Using a stack is O(n)\nHowever doing same in this question leads to Time Limit Exceeded.\n\nAn alternative to using stack is using a Tree data structure.\nWhy? Because tree will help me do binary search in O(log n) time. So I can find any interval or my place among intervals in O(log n).\nFunctions I will use are floor() and ceiling(). Please read about floor() and ceiling() here: https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html.\n\nAssumption: I will sort all intervals using "start".\n\nInsertion steps for newInterval:\n1. Datastructure: TreeSet. \n1. find floor() value for newInterval\n\ta. is previous mergeable into me? (previous.end >= newInterval.start)? \n\tb. YES: then remove previous and merge into newInterval.\n2. now I may merge intervals coming after me\n\ta. for each interval after me\n\t\t- is next mergable into me?\n\t\t- YES: remove next and merge it into newInterval\n3. Since all the elements mergeable into me are merged, just insert me into Tree.\n\nCode has two classes\nclass Interval - holds start, end, length, and has functions isMergeable() and merge().\nclass Solution - holds treeset, add() and count().\n\nInterval class\n```\nclass Interval implements Comparable<Interval> {\n    int start;\n    int end;\n    int len;\n    public Interval(int start, int end) {\n        this.start = start;\n        this.end = end;\n        this.len = end - start + 1;\n    }\n    \n    public void merge(Interval other) {\n        start = Integer.min(start, other.start);\n        end = Integer.max(end, other.end);\n        len = end - start + 1;\n    }\n    \n    public boolean isMergable(Interval other) {\n        return (start <= other.start && other.start <= end) \n            || (start <= other.end && other.end <= end) \n            || (other.start <= start && end <= other.end);\n    }\n    \n    public int compareTo(Interval other) {\n        if(start == other.start) {\n            return end - other.end;\n        } else {\n            return start - other.start;\n        }\n    }\n}\n```\n\nAnd the solution class\n```\nclass CountIntervals {\n    TreeSet<Interval> ts = new TreeSet();\n    int count = 0;\n    \n    public void add(int left, int right) {\n        Interval newInterval = new Interval(left, right);\n\n        // I may get merged into previous interval if my start < previous\' end.\n        Interval prev = ts.floor(newInterval);\n        if(prev != null && newInterval.isMergable(prev)) {\n            count -= prev.len;\n            ts.remove(prev);\n            newInterval.merge(prev);\n        }\n\n        // I may get merged into next interval(s) if my end > their start.\n        while(true) {\n            Interval next = ts.ceiling(newInterval);\n            if(next != null && newInterval.isMergable(next)) {\n                count -= next.len;\n                ts.remove(next);\n                newInterval.merge(next);\n            } else {\n                break;\n            }\n        }\n\n        ts.add(newInterval);\n        count += newInterval.len;   \n    }\n\n    public int count() {\n        return count;\n    }\n}\n```\n\nNow what is effective time complexity for each insertion?\nIt is O(log n) for floor(), ceiling(), remove() and insert().\nBut notice the infinite while loop - it runs for all elements after my start, that are mergeable into me. In worst case, that will happen to all the n elements present in Tree. \nSo for insertion, worst case time complexity is O(n log n).\n\nRemember that using stack has time complexity O(n)\nThis is worse than using a stack. However remember that "big O" time complexity only tells about worst case and cannot be always used to judge the best solution.
[]