[LeetCode] 15.Insert Interval (again)

leetcode.com/problems/insert-interval/

Insert Interval - LeetCode

 

1. Problem

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

2. Code

package leetCode;

import java.util.ArrayList;

public class insertInterval {

	public static void main(String[] args) {
		int[][] intervals = {{1,3},{6,9}};
		int[] newInterval = {2,5};
		insert(intervals, newInterval);
	}
	
	public static int[][] insert(int[][] intervals, int[] newInterval) {
		if(intervals.length == 0) {
			int[][] result = new int[1][2];
			result[0] = newInterval;
			return result;
		}
        int[]result = new int[2];
    	int size = 0;
    	//newInterval이 맨 앞이거나 맨 뒤일때
    	if(newInterval[1] < intervals[0][0] || newInterval[0] > intervals[intervals.length-1][1]) {
    		result = newInterval;
    	} else {       	
        	//newInterval이 중간에 있을때
            //result[0]
    		for(int i = 0; i < intervals.length; i++) {
            	//result[0]이 맨 앞일떄
            	if(newInterval[0] < intervals[0][0]) {
            		result[0] = newInterval[0];
            		break;
            	} //result[0]이 중간이고 배열 안에 있을때 
            	else if(newInterval[0] >= intervals[i][0] && newInterval[0] <= intervals[i][1]) {
            		result[0] = intervals[i][0];
            		break;
            		//result[0]이 중간이고 배열 밖에 있을때
            	} else if(newInterval[0] > intervals[i][1]) {
            		result[0] = newInterval[0];
            	} 
            }
    		//result[1]
    		for(int i = 0; i < intervals.length; i++) {
    			//result[1]이 중간이고 배열 안에 있을떄0
    			if(newInterval[1] >= intervals[i][0] && newInterval[1] <= intervals[i][1]) {
    				result[1] = intervals[i][1];
    				break;
    			} else if(newInterval[1] > intervals[i][1]) {
    				result[1] = newInterval[1];
    			}
    		}
            
    	}
    	
    	ArrayList resultList = new ArrayList();
    	//한 번 넣어주면 안넣음
    	boolean push = false;
    	//겹친 숫자 몇갠지
    	for(int i = 0 ; i < intervals.length; i++) {
    		if(result[0] <= intervals[i][0] && result[1] >= intervals[i][1])
    			size++;
    	}
    	// 앞에 위치할때 더하기
    	if(result[1] < intervals[0][0]) {
			resultList.add(result);
		}
    	
    	if(size == 0) {
    		for(int i = 0; i < intervals.length-1; i++) {
    			if(result[0] > intervals[i][1] && result[1] < intervals[i+1][0]) {
    				resultList.add(result);
    			}
    		}
    	} 
	    	for(int i = 0; i < intervals.length; i++) {
	    		if(!(result[0] <= intervals[i][0] && result[1] >= intervals[i][1])) {
	    			resultList.add(intervals[i]);
	    		}else if(!push) {
	    			resultList.add(result);
	    			push = true;
	    		}
	    	}
    	
    	if(result[0] > intervals[intervals.length-1][1]) {
 			resultList.add(result);
 		} 

    		int[][] resultArray = new int[resultList.size()][2];
    	for(int i = 0; i < resultList.size(); i++) {
    		resultArray[i] = (int[]) resultList.get(i);
    	}
    	
    	for(int i = 0 ; i < resultArray.length-1; i++) {
    		int[] temp = resultArray[i];
    		if(resultArray[i][0] > resultArray[i+1][0]) {
    			resultArray[i] = resultArray[i+1];
    			resultArray[i+1] = temp;
    		}
    	}
        return resultArray;
    }
}

 

3. Report

이 문제는 겹치지 않는 간격 세트가 주어지면 간격에 새 간격을 삽입하는 문제이다.

겹치는 부분은 합쳐준다.

일단 겹치지 않으면 newInterval을  result로 겹치면 합집합으로 result로 

result를 찾아주고

원래 intervals에서 적정한 위치에 result를 삽입해주었다

result 범위에 겹치는 원래의 배열들은 다 삭제해준다

 

for문은 intervals 길이만큼만 돌렸더니 result가 newInterval일때 resultList에 넣지 못하는 부분이 있어

앞에 사이에있으면 막 넣고 나중에 순서를 다시 정렬했다.>^^

 

개그지같이 푼문제

꼭한번 다시풀어보자 ^^...