My Binary Search Approach Implementation, 2ms
I know this is a little messy. For clean and simple code, please use the O(n) approach. We have great answer here with just 3 while loops. The BS approach utili
I know this is a little messy. For clean and simple code, please use the O(n) approach. We have great answer here with just 3 while loops. The BS approach utilizes the ordered characteristic of the input. For me, I want to get the position of the interval that is the first to have start equal to or larger than the inserted interval's start. Similarly, I get the position of the interval that is the first to have end equal to or larger than the new interval's end. Then I can get the range of intervals that the new interval connects. There are some corner cases that need to be considered, i.e. when the new interval has no overlap with any of the existing intervals (smaller, larger, or the original list is empty). In these corner cases, we just don't need to update the new interval. The code could possibly be cleaner and simpler without sacrificing the speed, or even with less time and space. Please let me know if you have any suggestions. Thank you!\n\n    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {\n        List<Interval> result = new ArrayList<>();\n        if (intervals == null || newInterval == null) return result;\n        int iStart = findStartPos(intervals, newInterval.start);\n        int iEnd = findEndPos(intervals, newInterval.end);\n        if (iStart > 0 && intervals.get(iStart - 1).end >= newInterval.start) iStart--;\n        if (iEnd == intervals.size() || intervals.get(iEnd).start > newInterval.end) iEnd--;\n        \n        //If not in the corner cases, this condition should apply.\n        if (iStart <= iEnd) {\n            newInterval = new Interval(Math.min(newInterval.start, intervals.get(iStart).start),Math.max(newInterval.end, intervals.get(iEnd).end));\n        }\n\n        int i = 0;\n        while (i < iStart) result.add(intervals.get(i++));\n        result.add(newInterval);\n        i = iEnd + 1;\n        while (i < intervals.size()) result.add(intervals.get(i++));\n        return result;\n    }\n    \n    private int findStartPos(List<Interval> intervals, int value) {\n        int l = 0, r = intervals.size() - 1;\n        while (l <= r) {\n            int m = (l + r) >> 1;\n            if (intervals.get(m).start == value) return m;\n            else if (intervals.get(m).start < value) l = m + 1;\n            else r = m - 1;\n        }\n        return l;\n    }\n    \n    private int findEndPos(List<Interval> intervals, int value) {\n        int l = 0, r = intervals.size() - 1;\n        while (l <= r) {\n            int m = (l + r) >> 1;\n            if (intervals.get(m).end == value) return m;\n            else if (intervals.get(m).end < value) l = m + 1;\n            else r = m - 1;\n        }\n        return l;\n    }
['Binary Tree', 'Java']