56. Merge Intervals

Problem Statement

Pattern: Related: 435. Non-Overlapping Intervals, 252 Meeting Rooms 253 Meeting Rooms II

---

Solution

public int[][] merge (int[][] intervals){
	// Sort by interval start
	Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
 
	ArrayList<int[]> res = new ArrayList<>();
	int[] currInterval = intervals[0];
	for(int[] newInterval: intervals) {
		if(newInterval[0] <= currInterval[1])
			// extend the end of the currInterval
			currInterval[1] = Math.max(currInterval[1], newInterval[1]);
		else {
			res.add(currInterval);
			// set newInterval as the currInterval
			currInterval = newInterval;
		}
	}
	res.add(currInterval);   // add the final currInterval
	return res.toArray(new int[0][]);
}

Notes

• iterate through all intervals
  • keep the currInterval to compare with the newInterval
  • if they overlap, extend the currInterval (update the end of currInterval to max(currInterval[1], newInterval[]))
  • once currInterval stops overlapping with newInterval, we add the now (extended ) currentInterval to res arraylist
• finally the last newInterval which is either extended in the if condition to the currInterval or is unique so gets set to currInterval in the else block. either ways the final newInterval ends up in currInterval so we add currInterval to result