Merge intervals
Hard
Java
Collections
22 views
Problem Statement
Task: given intervals, merge overlapping ones and return merged list.
Input Format
An integer n (number of intervals)
Then n lines, each with two integers:
start end
Then n lines, each with two integers:
start end
Output Format
List of merged intervals after combining all overlapping intervals.
Example
4 1 3 2 6 8 10 9 12
[1, 6] [8, 12]
Constraints
• n ≥ 0
• start ≤ end
• Intervals are integer ranges
• start ≤ end
• Intervals are integer ranges
Concept Explanation
Overlapping intervals are combined into one.
Intervals that do not overlap stay separate.
Intervals that do not overlap stay separate.
Step-by-Step Explanation
1.Read number of intervals n.
2.Store all intervals in a list (each as [start, end]).
3.Sort the intervals by start value in ascending order.
4.Create an empty list merged.
5.Take the first interval and add it to merged.
6.For each next interval:
• Let last be the last interval in merged.
• If current interval’s start ≤ last.end:
• Overlap exists → update last.end = max(last.end, current.end).
• Else:
• No overlap → add current interval to merged.
7.After processing all intervals, return or print merged.
2.Store all intervals in a list (each as [start, end]).
3.Sort the intervals by start value in ascending order.
4.Create an empty list merged.
5.Take the first interval and add it to merged.
6.For each next interval:
• Let last be the last interval in merged.
• If current interval’s start ≤ last.end:
• Overlap exists → update last.end = max(last.end, current.end).
• Else:
• No overlap → add current interval to merged.
7.After processing all intervals, return or print merged.
Concept Explanation
Overlapping intervals are combined into one.
Intervals that do not overlap stay separate.
Intervals that do not overlap stay separate.
Step-by-Step Explanation
1.Read number of intervals n.
2.Store all intervals in a list (each as [start, end]).
3.Sort the intervals by start value in ascending order.
4.Create an empty list merged.
5.Take the first interval and add it to merged.
6.For each next interval:
• Let last be the last interval in merged.
• If current interval’s start ≤ last.end:
• Overlap exists → update last.end = max(last.end, current.end).
• Else:
• No overlap → add current interval to merged.
7.After processing all intervals, return or print merged.
2.Store all intervals in a list (each as [start, end]).
3.Sort the intervals by start value in ascending order.
4.Create an empty list merged.
5.Take the first interval and add it to merged.
6.For each next interval:
• Let last be the last interval in merged.
• If current interval’s start ≤ last.end:
• Overlap exists → update last.end = max(last.end, current.end).
• Else:
• No overlap → add current interval to merged.
7.After processing all intervals, return or print merged.
Input / Output Format
Input Format
An integer n (number of intervals)
Then n lines, each with two integers:
start end
Then n lines, each with two integers:
start end
Output Format
List of merged intervals after combining all overlapping intervals.
Constraints
• n ≥ 0
• start ≤ end
• Intervals are integer ranges
• start ≤ end
• Intervals are integer ranges
Examples
Input:
4
1 3
2 6
8 10
9 12
Output:
[1, 6]
[8, 12]
Example Solution (Public)
static int[][] mergeIntervals(int[][] a){if(a.length==0) return new int[0][0];java.util.Arrays.sort(a,(x,y)->Integer.compare(x[0],y[0]));java.util.ArrayList<int[]> res=new java.util.ArrayList<>();int s=a[0][0],e=a[0][1];for(int i=1;i<a.length;i++){if(a[i][0]<=e){if(a[i][1]>e) e=a[i][1];}else{res.add(new int[]{s,e});s=a[i][0];e=a[i][1];}}res.add(new int[]{s,e});return res.toArray(new int[0][]);}
Official Solution Code
static int[][] mergeIntervals(int[][] a){if(a.length==0) return new int[0][0];java.util.Arrays.sort(a,(x,y)->Integer.compare(x[0],y[0]));java.util.ArrayList<int[]> res=new java.util.ArrayList<>();int s=a[0][0],e=a[0][1];for(int i=1;i<a.length;i++){if(a[i][0]<=e){if(a[i][1]>e) e=a[i][1];}else{res.add(new int[]{s,e});s=a[i][0];e=a[i][1];}}res.add(new int[]{s,e});return res.toArray(new int[0][]);}
Please login to submit solutions.