[알고리즘] Merge Intervals (O)

Problem

Key Point

종료 시간보다 큰 시작 시간이 나올 때 까지 before에 시간을 머지한다.

Code

public class MergeInterval {
    public List<Interval> solution(List<Interval> intervals) {
        if(intervals.isEmpty()) return intervals;
        List<Interval> result = new ArrayList<>();

        Collections.sort(intervals, (o1, o2) -> o1.getStart() - o2.getStart());
//        print(intervals);

        Interval before = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(i);
            if (before.getEnd() > current.getStart()) {
                before.setEnd(Math.max(before.getEnd(), current.getEnd()));
            } else {
                result.add(before);
                before = current;
            }
        }
        if (!result.contains(before)) {
            result.add(before);
        }
        print(result);
        return result;
    }
    private void print(List<Interval> intervals) {
        for (int i = 0; i < intervals.size(); i++) {
            Interval in = intervals.get(i);
            System.out.println(in.getStart() + " " + in.getEnd());
        }
    }
    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(new Interval(1, 3), new Interval(2, 6), new Interval(8, 10), new Interval(15, 18));
        MergeInterval mergeInterval = new MergeInterval();
        List<Interval> result = mergeInterval.solution(intervals);
    }
}