[알고리즘] merge-intervals (java 풀이)

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

Merge Intervals - LeetCode

 

문제

Given a collection of intervals, merge all overlapping intervals.

 

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

 

 

Example 2:

Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

 

문제 요약 : 배열 원소의 끝 부분과 다음 배열의 첫 부분이 겹치면 두 배열을 합쳐라.

 

 

-이 문제는 2차원 배열로 풀어도 되고, class를 만들어서 풀어도 된다.

 

import java.util.ArrayList;
import java.util.List;

class pair implements Comparable<pair> {
	int start;
	int end;

	pair() {
		start = 0;
		end = 0;
	}

	pair(int s, int e) {
		start = s;
		end = e;
	}

	@Override
	public int compareTo(pair o) {
		return this.start - o.start;
	}
}

public class MergeInterval {
	public static void main(String[] args) {

//		int[][] nums = {{1,3},{2,6},{8,10},{15,18}};
		pair in1 = new pair(1, 3);
		pair in2 = new pair(2, 6);
		pair in3 = new pair(8, 10);
		pair in4 = new pair(15, 18);

		List<pair> intervals = new ArrayList<>();
		intervals.add(in1);
		intervals.add(in2);
		intervals.add(in3);
		intervals.add(in4);

		List<pair> list = new ArrayList<>();

		pair before = intervals.get(0);
		for (int i = 1; i < intervals.size(); i++) {
			pair current = intervals.get(i);
			if (before.end >= current.start) {
				before.end = Math.max(before.end, current.end);
			} else {
				list.add(before);
				before = current;

			}
		}

		if (!list.contains(before)) {
			list.add(before);
		}

		print(list);

	}

	public static void print(List<pair> list) {
		for (int i = 0; i < list.size(); i++) {
			pair p = list.get(i);
			System.out.println(p.start + "," + p.end);
		}
	}

}

 

*주의할점은, for문을 다 돌고나서 before(맨 마지막 배열 요소)이 포함되어있는지 확인해야한다.