The inplace approach mainly uses an iterator and calls its remove() method when an overlapping occurs. If the input list is implemented as a linked list, this is a very smart approach because remove() in linked list costs O(1). Thus removing at most N times leads to a time complexity of O(N) and space complexity of O(1). However, if the input list is actually an arraylist, then each remove() will cost O(N) due to copying array elements, in the worst case we need O(N) removes, so the overall complexity will be O(N2). Is my understanding correct?
Java: Wouldn't the inplace approach degrade to O(N^2) when input is an ArrayList ?


I think you are right. Today, I used my inplace method to solve this problem, however, I got a LTE when the super long inputs coming in. In my method, the first step is to iterate all the Intervals and marked those need be removed. The second step is removing all the marked Intervals. My method should be O(n). So the point you mentioned is the reason why I got LTE in my idea.
public class Solution { public List<Interval> insert(List<Interval> intervals, Interval newInterval) { int size=intervals.size(); if(size==0) return intervals; int start=newInterval.start; int end=newInterval.end; boolean addnew=true; List<Integer> removeindexs=new ArrayList<Integer> (); for(int i=0;i<size;i++) { Interval temp=intervals.get(i); int ithstart=temp.start; int ithend=temp.end; if(start>=ithstart&&start<=ithend&&ithend<=end) { removeindexs.add(i); start=ithstart; } else if(end>=ithstart&&end<=ithend&&ithstart>=start) { removeindexs.add(i); end=ithend; } else if(ithstart>=start&&ithend<=end) { removeindexs.add(i); } else if(start>=ithstart&&end<=ithend) { addnew=false; break; } } int removesize=removeindexs.size(); for(int i=removesize1;i>=0;i) { intervals.remove(removeindexs.get(i)); } if(addnew) intervals.add(new Interval(start,end)); return intervals; } }