# A clean java solution

• ``````public class Solution {
public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval obj0, Interval obj1) {
return obj0.start - obj1.start;
}
});

List<Interval> ret = new ArrayList<>();
Interval prev = null;
for (Interval inter : intervals) {
if (  prev==null || inter.start>prev.end ) {
prev = inter;
} else if (inter.end>prev.end) {
// Modify the element already in list
prev.end = inter.end;
}
}
return ret;
}
}``````

• Thanks for the clean code!

• Concise java solution

``````public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if(intervals.size() <= 1) return intervals;

Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
for(int i = 0; i < intervals.size()-1; i++){
if(intervals.get(i).end >= intervals.get(i+1).start) {
intervals.get(i).end = Math.max(intervals.get(i).end,intervals.get(i+1).end);
intervals.remove(i+1);
i--;
}
}
return intervals;
}
}``````

• You use remove function, which will cost O(n) each time in worst case. That means, in your for loop, the time complexity is O(n^2).

• @dianren I delete the useless elements in the end to achieve a O(n) solution without extra space

``````public List<Interval> merge(List<Interval> intervals) {
if(intervals.size()<2) return intervals;
intervals.sort((Interval intervalA, Interval intervalB)->(intervalA.start - intervalB.start));
int index = 0; int remove = 0;
for(int i = 1; i<intervals.size(); i++){
if(intervals.get(index).end>=intervals.get(i).start){
intervals.get(index).end = Math.max(intervals.get(index).end,intervals.get(i).end);
remove++;
}
else{
index++;
intervals.get(index).start = intervals.get(i).start;
intervals.get(index).end = intervals.get(i).end;
}
}
while(remove-->0) intervals.remove(intervals.size()-1);
return intervals;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.