[LeetCode/MEDIUM] 56. Merge Intervals (JAVA) : 문제&풀이

 

 

Interval을 중복시간 없이 통합하는  문제이다.

 

인스턴스변수 start, end를 가진 Interval 클래스와

Interval 리스트를 매개변수로 받는 merge 메서드의 틀이 주어진다.

 

Problem :

class Interval {
    int start;
    int end;

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

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

public class MergeInterval {
    public List<Interval> merge(List<Interval> intervals) {

    }
}

풀이는 merge에 작성하면 된다.

 

Solution :

1. Interval 객체들이 담긴 intervals 리스트를 시작 시간 오름차순으로 정렬한다.
2. intervals 리스트를 순서대로 돌며
   1. 첫번째 Interval을 LinkedList에 담는다.
   2. 앞서 담은 Interval의 종료시간보다 다음 Interval의 시작시간이 빠르면 둘 중 종료시간이 더 늦은 시간으로 변경한다. (통합)
3. 결과 리스트를 반환한다.

import java.util.*;

class Interval {
    int start;
    int end;

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

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

public class MergeInterval {

    // time complexity : sort -> O(n log n)
    // space complexity : linkedList (copy of list 'intervals') -> O(n)
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.isEmpty()) return intervals;

        // sort
        Collections.sort(intervals, Comparator.comparingInt(o -> o.start));

        // merge
        LinkedList<Interval> result = new LinkedList<>();
        for (Interval interval : intervals) {
            if (result.isEmpty() || result.getLast().end < interval.start) {
                result.add(interval);
            } else {
                result.getLast().end = Math.max(result.getLast().end, interval.end);
            }
        }

        return result;
    }

 

이해하기 쉽게 그림으로 표현하면 다음과 같다.

 

Complexity :

• 시간복잡도 (Time Complexity)
  • Collections.sort에 따라 O(n log n)
• 공간복잡도 (Space Complexity)
  • 매개변수 intervals만큼 담아둘 LinkedList 사용에 따라 O(n)

 

Sample(Test) :

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Interval {
    int start;
    int end;

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

    Interval(int s, int e) {
        start = s;
        end = e;
    }
    
    @Override
    public String toString() {
        return "String.Interval { start = " + start + ", end = " + end + " }";
    }
}

public class MergeInterval {

    // time complexity : sort -> O(n log n)
    // space complexity : linkedList (copy of list 'intervals') -> O(n)
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.isEmpty()) return intervals;

        // sort
        Collections.sort(intervals, Comparator.comparingInt(o -> o.start));

        // merge
        LinkedList<Interval> result = new LinkedList<>();
        for (Interval interval : intervals) {
            if (result.isEmpty() || result.getLast().end < interval.start) {
                result.add(interval);
            } else {
                result.getLast().end = Math.max(result.getLast().end, interval.end);
            }
        }

        return result;
    }
    
    public static void main(String[] args) {
        List<Interval> intervals = Stream.of(
                new Interval(2, 5),
                new Interval(1, 6),
                new Interval(5, 10),
                new Interval(15, 20)
        ).collect(Collectors.toList());

        MergeInterval m = new MergeInterval();
        System.out.println(m.merge(intervals));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[String.Interval { start = 1, end = 10 }, String.Interval { start = 15, end = 20 }]