[LeetCode- Ch.2 정렬 & 검색] 6. interval 병합 ## (+ List to Arrays)

https://leetcode.com/problems/merge-intervals/submissions/

Merge Intervals - LeetCode

 

케이스 분류

1. 시작이 끝보다 클 때, 시작이 끝과 같을 때, 끝이 시작보다 크고도, 끝보다 작을 때

2.  처음에는 추가하지 않고 그 다음부터 추가하는데, 마지막은 반복문에서 추가하지 못하므로 따로 추가

 

import java.util.*;
class Solution {
    public int[][] merge(int[][] intervals) {
        //ArrayList<int []> list = new ArrayList<>();
        int N=intervals.length;

        //오름차순
        Arrays.sort(intervals, (o1, o2) -> {
            if(o1[0] == o2[0]){
                //내림차순
                return Integer.compare(o2[1], o1[1]);
            } else {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        
        ArrayList<int[]> list = new ArrayList<>();
        int start=Integer.MIN_VALUE;
        int end=Integer.MIN_VALUE;
        boolean flag=false;
        for(int[] x : intervals){
            if(x[0]>end) {
                if(flag) list.add(new int[] {start, end});
                start=x[0];
                end=x[1];
                flag=true;
            }else if(x[0]==end){
                end=x[1];
                flag=true;
            }
            else if(end>x[0] && end<x[1]){
                end=x[1];
            }
        }
        list.add(new int[] {start, end});
        
        int[][] answer=new int[list.size()][2];
        for(int i=0;i<list.size(); i++){
            answer[i]=list.get(i);
        }
        
        
        return answer;
     }
    }

---

+) 세련된 코드

print 함수 포함

class Solution {
    public int[][] merge(int[][] intervals) {
         List<int[]> res = new ArrayList<>();
        if(intervals.length == 0 || intervals == null) 
        	return res.toArray(new int[0][]);
        
        //1 ds
//        print(intervals);
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);//asc
//        System.out.println("==after=");
//        print(intervals);
        //2 for while
        
        int start =  intervals[0][0];
        int end = intervals[0][1];
        
//        for(int[] i : intervals) {
//        	if(end >= i[0]) {
//        	//4 >= 2
//        		end = Math.max(end, i[1]);//6
//        	}else {
//        		res.add(new int[] {start, end});
//        		start= i[0];
//        		end = i[1];
//        	}
//        }
        
        for(int i=1; i<intervals.length; i++) {
        	if(end >= intervals[i][0]) {
        	//4 >= 2
        		end = Math.max(end, intervals[i][1]);//6
        	}else {
        		res.add(new int[] {start, end});
        		start= intervals[i][0];
        		end = intervals[i][1];
        	}
        }
        
        
        res.add(new int[] {start, end});
//		return res.toArray(new int[0][]); 
		return res.toArray(new int[res.size()][]); 
    }


	private void print(int[][] grid) {
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				System.out.print(grid[i][j] + "\t");
			}
			System.out.println();
		}
	}

    
}

 

---

1. 시작값 기준 오름차순 정렬

2. 초기값 설정

3. 끝이 시작보다 크거나 같으면, 끝이 더 큰 값 설정

4. 끝이 시작보다 작으면, 해당 구간 추가

5. List를 Array로 변환

list.toArray(new int[list.size()][]);

 

class Solution {
    public int[][] merge(int[][] intervals) {
         List<int[]> res = new ArrayList<>();
        if(intervals.length == 0 || intervals == null) 
        	return res.toArray(new int[0][]);
        
        int start =  intervals[0][0];
        int end = intervals[0][1];

        
        for(int i=1; i<intervals.length; i++) {
        	if(end >= intervals[i][0]) {
        	//4 >= 2
        		end = Math.max(end, intervals[i][1]);//6
        	}else {
        		res.add(new int[] {start, end});
        		start= intervals[i][0];
        		end = intervals[i][1];
        	}
        }
        
        
        res.add(new int[] {start, end});
		return res.toArray(new int[res.size()][]); 
    }
}

 

---

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        int n=intervals.length;
        //1. 예외처리
        if(intervals.length == 0 || intervals == null) 
        	return list.toArray(new int[0][]);
        //2. 오름차순 정렬
        Arrays.sort(intervals, (a,b)->a[0]-b[0]);//asc

        //3. 초기값 설정
        int start=intervals[0][0];
        int end=intervals[0][1];
        
        //4. Loop
        //케이스 분류
        //끝 값이 시작값보다 같거나 클때는 끝 값만 갱신
        for(int i=1;i<n;i++){
            if(end>=intervals[i][0]){
                end=Math.max(intervals[i][1], end);
            }else{
                //끝 값보다 시작값이 크면 이전의 시작->끝을 리스트에 추가
                //새로운 값을 시작과 끝에 저장
                list.add(new int[]{start,end});
                start=intervals[i][0];
                end=intervals[i][1];
            }
        }
        
        //마지막 값은 따로 저장 필요
        list.add(new int[]{start,end});
        //5. 리턴값 설정
        //list->Array 변환
        return list.toArray(new int[list.size()][]);
    }
}