[Leetcode] 57. Insert Interval

문제)

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

 

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Example 3:

Input: intervals = [], newInterval = [5,7] Output: [[5,7]]

Example 4:

Input: intervals = [[1,5]], newInterval = [2,3] Output: [[1,5]]

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7] Output: [[1,7]]

 

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 105
• intervals is sorted by intervals[i][0] in ascending order.
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 105

 

풀이)

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] arr = new int[intervals.length+1][2];
        System.arraycopy(intervals, 0, arr, 0, intervals.length);
        arr[intervals.length] = newInterval;
        Arrays.sort(arr, (a,b) -> Integer.compare(a[0], b[0]));
        LinkedList<int[]> merged = new LinkedList<>();
        for(int[] interval : arr) {
            if(merged.isEmpty() || merged.getLast()[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.getLast()[1] = Math.max(interval[1], merged.getLast()[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

1. 설명
 - 방법은 https://strange-developer.tistory.com/62와 동일
 - 다른점은 처음에 Insert하고 sorting한다는 점.

 

2. 제출결과

 

3. 시간복잡도

O(nlogn)

 

다른사람 풀이)

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> list = new ArrayList<>();
        for (int[]interval : intervals) {
            int curStart = interval[0];
            int curEnd = interval[1];
            if (curEnd < start) {
                list.add(new int[]{curStart, curEnd});
            } else if (curStart > end) {
                list.add(new int[]{start, end});
                start = curStart;
                end = curEnd;
            } else {
                start = Math.min(start, curStart);
                end = Math.max(end, curEnd);
            }  
        }
        list.add(new int[]{start, end});
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i][0] = list.get(i)[0];
            res[i][1] = list.get(i)[1];
        }
        return res;
    }      
}

1. 설명

- 주어진 interval 배열은 이미 정렬되어있으므로, 상관관계가 있는 interval들을 하나로 합쳐서 리스트로 던지면 됨.

- 즉, start와 end를 통해 하나의 값으로 만들고, 더 이상 포함관계에 있지 않으면 리스트에 추가시킴

- 일반 배열은 add() 함수를 통해 배열의 마지막 위치에 값을 추가시키지 못하므로, list로 결과값을 만들고, array로 변환시키는 작업을 마지막에 함.

 

2. 제출결과

3. 시간복잡도

O(n)