Java 2ms O(log n)/O(1) binary search solution beats 97.7% with clear explaination
The idea is using binary search to find the position that the newInterval to be inserted. \n\nSince the original intervals are sorted and disjoint, we can apply
The idea is using binary search to find the position that the newInterval to be inserted. \n\nSince the original intervals are sorted and disjoint, we can apply binary search to find the insertion index of newInterval.start (by interval.start), and to find the insertion index of newInterval.end(by interval.end), \u3010see LeeCode problem #35\u3011. Then remove the overlapped elements of the list and merge the newInterval with boundary elements on two sides.\n\nComplexity: O(log n) in time (in fact, depending on the implement of the access method list.get(i) and of list.subList(int, int).clear()); O(1) in space.\n\n    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {\n\t\t\t/**\n\t\t\t * Since the original list is sorted and all intervals are disjoint,\n\t\t\t * apply binary search to find the insertion index for the new\n\t\t\t * interval. [LC35]\n\t\t\t * \n\t\t\t * 1. Find insIdx=the insertion index of new.start, i.e., the first\n\t\t\t * index i such that list.get(i).start>=new.start.\n\t\t\t * \n\t\t\t * 2. Find nxtIdx=the insertion index of new.end, i.e., the first\n\t\t\t * index i such that list.get(i).end>=new.end.\n\t\t\t * \n\t\t\t * 3. Remove all elements of the list with indices insIdx<=i<nxtIdx.\n\t\t\t * \n\t\t\t * 4. Merge new with list.get(insIdx-1) or list.get(nxtIdx) or both.\n\t\t\t */\n\n\t\t\tint n = intervals.size();\n\t\t\tif (n == 0) {\n\t\t\t\tintervals.add(newInterval);\n\t\t\t\treturn intervals;\n\t\t\t}\n\n\t\t\tint low = 0, high = n - 1, mid = 0;\n\t\t\tint temp, target = newInterval.start;\n\t\t\twhile (low <= high) {\n\t\t\t\tmid = (low + high) / 2;\n\t\t\t\ttemp = intervals.get(mid).start;\n\t\t\t\tif (temp == target)\n\t\t\t\t\tbreak;\n\t\t\t\tif (temp < target)\n\t\t\t\t\tlow = mid + 1;\n\t\t\t\telse\n\t\t\t\t\thigh = mid - 1;\n\t\t\t}\n\n\t\t\t// insIdx = the index where new interval to be inserted\n\t\t\tint insIdx = (low <= high) ? mid : low;\n\t\t\tInterval pre = (insIdx == 0) ? null : intervals.get(insIdx - 1);\n\t\t\t// 0<=insIdx<=n, pre=[insIdx-1], pre.start<new.start\n\n\t\t\tlow = insIdx;\n\t\t\thigh = n - 1;\n\t\t\ttarget = newInterval.end;\n\t\t\twhile (low <= high) {\n\t\t\t\tmid = (low + high) / 2;\n\t\t\t\ttemp = intervals.get(mid).end;\n\t\t\t\tif (temp == target)\n\t\t\t\t\tbreak;\n\t\t\t\tif (temp < target)\n\t\t\t\t\tlow = mid + 1;\n\t\t\t\telse\n\t\t\t\t\thigh = mid - 1;\n\t\t\t}\n\n\t\t\t// nxtIdx= the next index after the inserted new interval\n\t\t\tint nxtIdx = (low <= high) ? mid : low;\n\t\t\tInterval nxt = (nxtIdx == n) ? null : intervals.get(nxtIdx);\n\t\t\t// insIdx<=nxtIdx<=n, nxt=[nxtIdx], nxt.end>=new.end\n\n\t\t\t// [0]...[insIdx-1] <--> [insIdx]...[nxtIdx-1][nxtIdx]...[n]\n\t\t\tintervals.subList(insIdx, nxtIdx).clear();\n\n\t\t\t// check whether newInterval can be merged with pre or nxt\n\t\t\tboolean isMerged = false, isMerged2 = false;\n\t\t\tif (insIdx > 0 && pre.end >= newInterval.start) {\n\t\t\t\tpre.end = Math.max(pre.end, newInterval.end);\n\t\t\t\tisMerged = true;\n\t\t\t}\n\n\t\t\tif (nxtIdx < n && newInterval.end >= nxt.start) {\n\t\t\t\tnxt.start = Math.min(nxt.start, newInterval.start);\n\t\t\t\tisMerged2 = isMerged;\n\t\t\t\tisMerged = true;\n\t\t\t}\n\n\t\t\tif (!isMerged) {\n\t\t\t\tintervals.add(insIdx, newInterval);\n\t\t\t\treturn intervals;\n\t\t\t}\n\n\t\t\t// merged with pre or nxt or both, deal with the both case\n\t\t\tif (isMerged2 && pre.end >= nxt.start) {\n\t\t\t\tnxt.start = pre.start; // pre.start < new.start, nxt.start;\n\t\t\t\tintervals.remove(insIdx - 1); // remove pre\n\t\t\t}\n\n\t\t\treturn intervals;\n\t\t}
['Binary Tree', 'Java']