[Leetcode][56. Merge Intervals] 56. Merge Intervals 코딩 인터뷰 문제풀이 Java

56. Merge Intervals 문제풀이

Merge Intervals - LeetCode

Example 1:Input: intervals = [[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: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

 

JAVA Solution;

 public int[][] merge(int[][] intervals) {
    0. return input parameters when intervals.length <=1
    1. sort the intervals ascending order by first point
    2. create a new output array for the output, called `newInterval` and save the 
    	first value into result
    3. when newInterval[0] >= currentInterval[0], 
    	newInterval[1] = Math.max(newIntervals[1], currentInterval[1]
    4. otherwise, add the currentInterval to the newIntervals 
    	as there is no overlapping values
        
   if(intervals.length < =1 ) return intervals;
   Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));
   
   List<Integer> result = Lists.newArrayList();
   int[] newInterval = intervals[0];
   result.add(newInterval);
   
   for(int[] currentInterval : intervals) {
     if(newInterval[1] >= currentInterval[0]) { 
        newInterval[1] = Math.max(currentInterval[1], newInterval[1]);
     }
     else {
        newInterval = interval;
        result.add(newInterval);
     } 
   }
   return result.toArray(new int[result.size()][2]);
 }

Time, Space Complexity:

• Time Complexity: O(n log n); since sort() has been used
• Space Complexity: O(n log n); since sort() has been used