[Misc][Medium] 56. Merger Intervals.

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

 

Q. 구간의 배열이 주어질 때, 겹치는 구간에 작은 구간을 포함 할 수 있다. 

 이렇게 Merge를 하라. 

 

Solution. 

 두 구간 값을 cX, cY 라고 해 본다.

 예제를 보면 알 수 있지만, 핵심은 cY와 다음의 cX 가 겹치는가가 중요하게 작용을 한다. 

 즉, 현재의 cY가 다음의 cX 보다 크거나 같으면, 현재 구간을 다음 구간과 병합하면 되는 것이다. 

 다만, 이 전에 cX에 대해 모든 두간 배열이 정렬되어 있어야 하겠다. 

 

 로직대로 코드를 만들어 본다. 

 

 

public int[][] Merge(int[][] intervals) 
{
    Array.Sort(intervals, (a, b) => 
    {
        if(a[0] > b[0])         return 1;
        else if(a[0] < b[0])    return -1;
        return 0;
    });

    List<int[]> ret = new List<int[]>();
    int cX = intervals[0][0];
    int cY = intervals[0][1];
    for(int q = 1; q < intervals.Length; ++q)
    {
        if(cY >= intervals[q][0])
            cY = Math.Max(cY, intervals[q][1]);
        
        else 
        {
            ret.Add(new int[]{cX, cY});
            cX = intervals[q][0];
            cY = intervals[q][1];
        }
    }
    ret.Add(new int[]{cX, cY});
    return ret.ToArray();
}

 

적절한 결과.