[PS] MergeIntervals Solution in Java

Leetcode MergeIntervals Solution

문제설명

불규칙하게 들어오는 배열의 범위를 Merge 한 배열을 찾는 것

 

Input
[[1,3],[2,6],[8,10],[15,18]]

Output

[[1,6],[8,10],[15,18]]

 

Input Output 설명

1,3과 2,6 은 겹치는 구간이 있으므로 merge 된것

코드

public class MergeIntervals {
    //javaxf Pair doesn't work at leetcode TT
    class Pair {
        Integer key;
        Integer value;

        public Pair(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }

        public Integer getKey() {
            return key;
        }

        public Integer getValue() {
            return value;
        }
    }

    public int[][] merge(int[][] intervals) {
    	// '[]' validation
        if(intervals.length == 0) {
            return intervals;
        }

	//배열 정렬(sort the array)
        Arrays.sort(intervals, (o1, o2) -> {
            if(o1[0] == o2[0]) {
                return Integer.compare(o1[1], o2[1]);
            }
            return Integer.compare(o1[0], o2[0]);
        });

        List<Pair> ans = new ArrayList<>();

        int minn = intervals[0][0];
        int maxx = intervals[0][1];

        for(int i =0 ; i < intervals.length; i++) {
            if(i == intervals.length -1) {
                ans.add(new Pair(minn, maxx));
            } else if(maxx < intervals[i+1][0]) {
                ans.add(new Pair(minn, maxx));
                minn = intervals[i+1][0];
                maxx = intervals[i+1][1];
            } else if ( maxx < intervals[i+1][1] ) {
                maxx = intervals[i+1][1];
            }
        }

        return ans.stream()
                   .map(pair -> new int[] {pair.getKey(),pair.getValue()})
                   .toArray(int[][]::new);
    }
}

 

Sort 하는 부분에 대한 설명:  https://ramees.tistory.com/53

 

들어오는 배열을 sort 한 후 부터는 쉬워진다. 값을 보고 비교하면 된다.

 

[Java] 자바로 2차원 배열 2번째 element 까지 정렬하기, Comparator

 

끝!