Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@rezaiyan
Last active April 5, 2019 10:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rezaiyan/49d9ad7409b04474b3da896213c3f69e to your computer and use it in GitHub Desktop.
Save rezaiyan/49d9ad7409b04474b3da896213c3f69e to your computer and use it in GitHub Desktop.
Given a collection of intervals, merge all overlapping intervals.
/*
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
*/
public List<Interval> merge(List<Interval> intervals) {
int currentIndex = 0, iteratorIndex = 1;
while (iteratorIndex < intervals.size() && currentIndex < intervals.size()){
Interval current = intervals.get(currentIndex);
Interval next = intervals.get(iteratorIndex);
if (current.end >= next.start && current.start <= next.end && iteratorIndex != currentIndex) {
intervals.get(currentIndex).end = current.end < next.end ? next.end : current.end;
intervals.get(currentIndex).start = current.start < next.start ? current.start : next.start;
intervals.remove(next);
iteratorIndex = currentIndex;
} else {
iteratorIndex++;
}
if (iteratorIndex == intervals.size()) {
iteratorIndex = currentIndex;
currentIndex++;
}
if (currentIndex == intervals.size()) {
iteratorIndex++;
currentIndex = 0;
}
}
return intervals;
}
@rezaiyan
Copy link
Author

rezaiyan commented Apr 1, 2019

This solution has "Time Limit Exceeded" error for large inputs.
@farsialgorithm
could you help me to improve this snippet code.

@rezaiyan
Copy link
Author

rezaiyan commented Apr 5, 2019

Success

Runtime: 7 ms, faster than 94.57% of Java online submissions for Merge Intervals.
Memory Usage: 39.2 MB, less than 97.89% of Java online submissions for Merge Intervals.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment