Binary Search solution
First looking where to insert elements from new interval using binary search (to left of the interval or into the interval itself) - O(log N). Second composing 
First looking where to insert elements from new interval using binary search (to left of the interval or into the interval itself) - O(log N). Second composing two lists left and right to the new interval. Third merging if start or end falls in between of any interval. Overall worst case still O(N) but binary search helps in cases like new interval consumes all intervals.\n\n**Python**\n```\n    def bsearch(intervals: List[List[int]], x: int) -> int:\n        lo, hi = 0, len(intervals)\n        mid = 0\n        while lo < hi:\n            mid = (lo + hi) // 2\n            if intervals[mid][0] > x:\n                hi = mid\n            elif intervals[mid][1] < x:\n                lo = mid + 1\n            else:\n                break\n        return mid\n \n    def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        s, e = newInterval\n        li, ri = bsearch(intervals, s), bsearch(intervals, e)\n        l = intervals[:li + int(li < len(intervals) and intervals[li][1] < s)]\n        r = intervals[ri + int(ri >= len(intervals) or intervals[ri][0] <= e):]\n        if len(l) + len(r) != len(intervals):\n            s = min(s, intervals[len(l)][0])\n            e = max(e, intervals[-len(r)-1][1])\n        return l + [[s, e]] + r\n```\n\n**Javascript**\n```\nconst bsearch = (intervals, x) => {\n    let mid = 0;\n    let lo = 0;\n    let hi = intervals.length;\n    while (lo < hi) {\n        mid = (lo + hi - Number((lo + hi) % 2 !== 0)) / 2;\n        if (intervals[mid][0] > x)\n            hi = mid;\n        else if (intervals[mid][1] < x)\n            lo = mid + 1\n        else\n            break;\n    }\n    return mid;\n}\n\nconst insert = (intervals, newInterval) => {\n    let [s, e] = newInterval;\n    const li = bsearch(intervals, newInterval[0]);\n    const ri = bsearch(intervals, newInterval[1]);\n    const l = intervals.slice(0, li + Number(li < intervals.length && intervals[li][1] < s));\n    const r = intervals.slice(ri + Number(ri >= intervals.length || intervals[ri][0] <= e))\n    if (l.length + r.length !== intervals.length) {\n        s = Math.min(s, intervals[l.length][0]);\n        e = Math.max(e, intervals[intervals.length - r.length - 1][1]);\n    }\n    return [...l, [s, e], ...r];\n};\n```\n\n**Rust**\n```\n    use std::cmp::Ordering;\n    fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {\n        let (mut s, mut e) = (new_interval[0], new_interval[1]);\n        let pred = |x| {\n            move |i: &Vec<i32>| {\n                if i[0] > x {\n                    Ordering::Greater\n                } else if i[1] < x {\n                    Ordering::Less\n                } else {\n                    Ordering::Equal\n                }\n            }\n        };\n        let li = intervals.binary_search_by(pred(s)).unwrap_or_else(|x| x);\n        let ri = intervals.binary_search_by(pred(e)).unwrap_or_else(|x| x);\n        let l = &intervals[..(li + usize::from(li < intervals.len() && intervals[li][1] < s))];\n        let r = &intervals[(ri + usize::from(ri >= intervals.len() || intervals[ri][0] <= e)).min(intervals.len())..];\n        if l.len() + r.len() != intervals.len() {\n            s = s.min(intervals[l.len()][0]);\n            e = e.max(intervals[intervals.len() - r.len() - 1][1]);\n        }\n        vec![l, &vec![vec![s, e]], r].concat()\n    }\n```
['Binary Tree', 'Python', 'Rust']