Merge Interval

시작과 끝 시간이 담긴 Interval 배열에서 겹치는 시각의 회의는 합병하고 겹치지 않는 시간의 회의는 그대로 두어 새로운 배열을 리턴하자.

 

개인적으로 풀기에는 이렇게 했다.

• 길이가 가변적이기 때문에 List 를 쓰게 됬다.
• start 와 end 변수를 두어 합병할 데이터를 저장해두려했다.
• 만약 합병 데이터 저장 후 또다른 데이터도 합병해야한다면 start는 그대로 둬야만한다.
• 합병할 조건에 맞지 않을때 합병데이터 있을경우 합병데이터로 Interval을 만들고, 현재 원소도 add한다.
• 합병데이터가 없고, 합병 조건도 맞지 않을경우 그대로 add 한다.
• List 를 Array로 치환한다.

public class MergeInterval {
    public static void main(String[] args) {
        Interval interval1 = new Interval(1, 3);
        Interval interval2 = new Interval(2, 6);
        Interval interval3 = new Interval(8, 10);
        Interval interval4 = new Interval(15, 18);
        Interval[] intervals = new Interval[]{interval1, interval2, interval3, interval4};

        Interval[] answer = solve(intervals);
        System.out.println("=================== result =================");
        System.out.println(Arrays.toString(answer));
    }

    /**
     * 길이가 가변적이라 list를 쓴다.
     * 합병할 데이터인 start 와 end를 지정한다.
     * for문을 돌고 배열의 전 원소의 end가 현재 원소의 start 보다 크다면 start 와 end에 전 원소의 start, 현 원소의 end를 넣는다.
     * 이때 만약 start에 값이 들어있는 상태라면, start 값은 그대로 제일 작은 start 값으로 가진다.
     *
     * 다음 루프시에 start와 end 값이 0 이 아니라면, start와 end로 Interval을 만들어 add 하고 현재 루프중인 원소도 add 한다.
     *
     * 합병되지 않는 원소거나, 전에 합병할 데이터가 없을 경우 그냥 저장한다.
     *
     * list 를 Array로 치환해서 리턴한다.
     */
    private static Interval[] solve(Interval[] intervals) {
        List<Interval> list = new ArrayList<>();

        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        } );

        int start = 0;
        int end = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i-1].end > intervals[i].start) {
                start = start == 0? intervals[i-1].start : start ;
                end = intervals[i].end;
            } else if(start != 0 && end != 0) {
                list.add(new Interval(start, end));
                start = 0;
                end = 0;//기존에 합병할 값을넣고 해당 원소도 넣는다
                list.add(intervals[i]);
            } else {
                list.add(intervals[i]);
            }
        }

        return list.toArray(new Interval[]{});
    }
}

---

핵심 : 마지막 원소에 대한 고려, for 문 바깥에 정의한 Interval

• 람다로 sorting 
• 새로운 그릇으로 List 를 정하고
• for문 바깥에 첫원소를 담은 Interval 을 선언하여 for 문이 1부터 돌게 한다.
• 현재 원소를 가져와 값을 비교한뒤 합병해야하면 before 만 바꾼다.(Math.max)
• 합병하지 않는 조건이 올경우 그릇에 befored를 담고 before를 current 로 채운다.
• 루프된 현재 원소를 기준으로 다시 before와 비교한다.
• 루프 상 마지막원소는 등록되지않고 before에 남게되므로 마지막 원소를 채워준다.

public class MergeIntervalTeaching {
    public static void main(String[] args) {
        Interval interval1 = new Interval(1, 3);
        Interval interval2 = new Interval(2, 6);
        Interval interval3 = new Interval(8, 10);
        Interval interval4 = new Interval(15, 18);

        List<Interval> intervals = Arrays.asList(new Interval[]{interval1, interval2, interval3, interval4});

        List<Interval> answer = merge(intervals);
        System.out.println("================result==================");
        answer.forEach(interval -> System.out.println(interval));
    }

    /**
     * sort 가 필요
     * 그릇은 List
     */
    private static List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, (o1, o2) -> o1.start - o2.start);
        List<Interval> result = new ArrayList<>();
        intervals.forEach(interval -> System.out.println(interval));

        //병합을 어떻게
        Interval before = intervals.get(0);//[1,3] for문 바깥에 저장할 객체를 가져온다.
        for (int i = 1; i < intervals.size(); i++) {// 1부터 시작
            // 루프 값을 가져옴
            Interval current = intervals.get(i);

            if (before.end >= current.start) {
                before.end = Math.max(before.end, current.end); // before 를 조작
            } else {
                result.add(before);
                // **** 현재 루프 값을 외부의 before로 바꾼다.
                before = current;
            }
        }

        //마지막 원소에 대한 고려 ***********
        if (!result.contains(before)) {
            result.add(before);
        }
        return result;
    }
}