Last active
April 5, 2019 10:38
-
-
Save rezaiyan/49d9ad7409b04474b3da896213c3f69e to your computer and use it in GitHub Desktop.
Given a collection of intervals, merge all overlapping intervals.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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; | |
} |
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
This solution has "Time Limit Exceeded" error for large inputs.
@farsialgorithm
could you help me to improve this snippet code.