public class Solution
{
public List<Interval> merge(List<Interval> intervals)
{
if(intervals.size()<2) return intervals;
int count=0;
//If no more merge can be done,
//then counting when traversing the list through will give out the size of list.
while(count<intervals.size())
{
int before=intervals.size();
//My algorithm guarantee the first element of the list is the one hasn't been checked.
Interval temp=intervals.remove(0);
int a=temp.start, b=temp.end;
for(int i=0; i<intervals.size(); i++)
{
temp=intervals.get(i);
int c=temp.start, d=temp.end;
if(b>=c&&d>=a)
{
intervals.remove(i);
i; //i is crucial since the list shrunk after removal.
a=Math.min(a,c);
b=Math.max(b,d);
}
}
//Putting temporarily merged interval at the end.
intervals.add(new Interval(a,b));
if(before==intervals.size()) count++;
else count=0;
}
return intervals;
}
}
Why sort? Why extra memory space? Challenge me if you have a more elegant solution.


First of all, allow me to say that the time complexity of your solution is O(n^2), which is worse than O(nlog n). If you sort the input at first, which takes O(nlog n), then you can liner scan the list and do the merge in O(n) time. Thus the final time complexity is O(n log n ). The merge can be done in the sort process, if you write the sort by yourself. Secondly, the runtime on leetcode is meaninless. As you can see, the runtime of the same code can be various even submiting in the same time period

I appreciate your comments, but I have to say that, for many cases, two loops don't necessarily mean O(n^2). Let k be the length of of the answer list of nonoverlapping intervals denoted by S, then in the first run, S0 will consume all those intervals overlapping with it, meaning that, in the second run, less than n intervals needed to be compared. I do shared your opinion about O(n^2) in the worst input scenario, in which any two intervals are disjoint, so it takes n^2. However, in most input scenarios, the first few runs can prune out most of n intervals within the input, meaning that we are very likely to have a constant*n runtime. By the way, with the respect of memory usage, mine does the best.

I had similar thought at the very first. And solution without sorting ends up being extremely fast (Beat 96~98%)... But it should be O(N^2) indeed, right? So I assume that is the test data set problem maybe it's not large enough?
public List<Interval> merge(List<Interval> intervals) { List<Interval> result = new ArrayList<>(); for (Interval interval : intervals) doMergeOne(result, interval); return result; } private void doMergeOne(List<Interval> merged, Interval interval) { int i = 0; for (; i < merged.size() && merged.get(i).end < interval.start; i++); while (i < merged.size() && merged.get(i).start <= interval.end) { interval = new Interval(Math.min(merged.get(i).start, interval.start), Math.max(merged.get(i).end, interval.end)); merged.remove(i); } merged.add(i, interval); }