[JAVA][Array] MergeInterval

1. 문제

Given a collection of intervals, merge all overlapping intervals.

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

 

2. 문제해설

겹치는 부분을 통합하여라(ex, Input: [1,3],[2,6], Output:[1,6])

 

3. 코드포맷

class Interval {
	int start;
	int end;

	Interval() {
		this.start = 0;
		this.end = 0;
	}

	Interval(int s, int e) {
		this.start = s;
		this.end = e;
	}

	@Override
	public String toString() {
		return start + ", "+end;
	}
	
}

public class MergeInterval {
	public static void main(String[] args) {
		Interval in1 = new Interval(1, 3);
		Interval in2 = new Interval(2, 6);
		Interval in3 = new Interval(7, 8);
		Interval in4 = new Interval(7, 10);
		Interval[] intervals = { in1, in2, in3,in4 };
		MergeInterval a = new MergeInterval();
		List<Interval> list = a.merge(intervals);
		a.print(list);
	}
}

 

4. 접근 방법

1) Input에 있는 각 배열의 0번인덱스를 기준으로 정렬

2) 정렬된 Input 기준으로 i번째 배열의 end 부분과 i+1번째 배열의 start를 비교한다.

5. 코드

public class MergeInterval {
	public static void main(String[] args) {
		Interval in1 = new Interval(1, 3);
		Interval in2 = new Interval(2, 6);
		Interval in3 = new Interval(7, 8);
		Interval in4 = new Interval(7, 10);
		Interval[] intervals = { in1, in2, in3, in4 };
		MergeInterval a = new MergeInterval();
		List<Interval> list = a.merge(intervals);
		a.print(list);
	}

	private List<Interval> merge(Interval[] intervals) {
		List<Interval> list = new ArrayList<Interval>();
		//정렬
		Arrays.sort(intervals,comp);
		//merge 과정속에서 담을 그릇
		Stack<Interval> stack = new Stack<Interval>();
		
		for(int i=0;i<intervals.length;i++) {
			//stack이 비어있지 않고 stack에 담긴 i-1번째의 end값과 i번째의 start를 비교하여 end가 크다면 i번째의 end로 수정한다.
			if(!stack.isEmpty() && stack.peek().end>=intervals[i].start) {
				stack.peek().end=intervals[i].end;
			}
			else {
				stack.push(intervals[i]);
			}
		}
		for(Interval i : stack) {
			list.add(i);
		}
		return list;
	}

	Comparator<Interval> comp = new Comparator<Interval>() {
		@Override
		public int compare(Interval o1, Interval o2) {
			return o1.start-o2.start;
		}
	};
	
	// 출력부분
	private void print(List<Interval> list) {
		for (Interval i : list) {
			System.out.println(i);
		}
	}

}