# Merge while merge-sorting

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

int n = intervals.size();

List<Interval> left = merge(new ArrayList<>(intervals.subList(0, n/2)));
List<Interval> right = merge(new ArrayList<>(intervals.subList(n/2, n)));

int lSize = left.size();
int rSize = right.size();
List<Interval> result = new ArrayList<>();
Interval cur = null;

while (lSize > 0 && rSize > 0) {
Interval l = left.remove(0);
Interval r = right.remove(0);
boolean merged = false;

if (cur == null) {
if (l.start < r.start) cur = r;
else cur = l;
}
Interval combine = mergeTwo(l, cur);
if (combine != null) {
cur = combine;
lSize--;
merged = true;
} else {
}

combine = mergeTwo(r, cur);
if (combine != null) {
cur = combine;
rSize--;
merged = true;
} else {
}

if (!merged) {
cur = null;
}
}

while (lSize > 0) {
Interval i = left.remove(0);
if(cur == null) cur = i;
Interval combine = mergeTwo(i, cur);
if (combine != null) {
cur = combine;
lSize--;
} else {
cur = null;
}
}
while (rSize > 0) {
Interval i = right.remove(0);
if(cur == null) cur = i;
Interval combine = mergeTwo(i, cur);
if (combine != null) {
cur = combine;
rSize--;
} else {
cur = null;
}
}
return result;
}

public Interval mergeTwo(Interval a, Interval b) {
if ((b.start >= a.start && b.start <= a.end) ||
(b.end >= a.start && b.end <= a.end) ||
(a.start >= b.start && a.start <= b.end) ||
(a.end >= b.start && a.end <= b.end)
) {
int start = Math.min(a.start, b.start);
int end = Math.max(a.end, b.end);
return new Interval(start, end);
} else {
return null;
}
}
}
``````

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