# Java Different approach, O(nlogn) time O(n) space

• Not the best solution space wise - just took a slightly different approach. Its based on the observation that start points of merged intervals will always come before the end point of that original interval. So on a set sorted by the start points, we add 1 to a count every time we reach a start point, end decrease 1 when we reach an end point. If the count is zero the interval is complete.

public class Solution {

private class Point implements Comparable<Point> {
int val;
boolean isEnd;

public Point(int val, boolean isEnd) {
this.val = val;
this.isEnd = isEnd;
}

public int compareTo(Point other) {
return (val - other.val == 0 ? (isEnd ? 1 : -1) : val - other.val);
}
}

public List<Interval> merge(List<Interval> intervals) {
TreeSet<Point> points = new TreeSet<>();
List<Interval> result = new ArrayList<>();

for (Interval interval : intervals) {
}

Interval currInterval = null;

int count = 0;
for (Point point : points) {
if (count == 0) {
currInterval = new Interval();
currInterval.start = point.val;
count = 1;
} else if (point.isEnd) {
count--;
if (count == 0) {
currInterval.end = point.val;
count = 0;
}
} else {
// Means this is a starting point of a merged interval.
count++;
}
}

return result;
}

}

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