[Interval][Medium] 435. Non-overlapping Intervals.

https://leetcode.com/problems/non-overlapping-intervals/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. start와 end로 이루어진 다수의 interval들이 input으로 주어진다. 겹치는 구간이 존재할때, 이 겹치는 구간을 제거해서 interval이 겹쳐지지 않도록 하라. 이때 이 제거하게 되는 최소한의 interval의 수를 구하라. 

 

 

S.  예제에서 보듯이 interval들이 주어진다. 

 우선 겹치는 구간을 찾아야 한다. 

 또한 그 구간 중 크게 겹쳐지는 것을 제거해야 최소한의 제거로 많은 겹치는 구간을 해소 할 수 있을 것이다. 

 

 예제에서 보듯이 겹치는 구간을 쉽게 찾기 위해서는 input을 정렬해야 한다. 

 이후 순서대로 순회하며, 찾아낸 겹치는 구간 중 큰 녀석을 제거한다. 

 

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

 

// start의 크기대로 interval을 정렬한다.
// 이때 parameter는 최적화를 위해 반드시 reference type으로 전달한다.
static bool interval_sort(vector<int>& v1, vector<int>& v2)
{
    return v1[0] < v2[0];
}

int eraseOverlapIntervals(vector<vector<int>>& in) 
{
    if (in.size() <= 1)	return 0;

    sort(in.begin(), in.end(), interval_sort);

    int minRet = 0;
    int preEnd = in[0][1];
    for (int k = 1; k < in.size(); ++k)
    {
        // 현재 시작이 이전 끝보다 작다면 겹쳐진다.
        if (in[k][0] < preEnd)
        {
            ++minRet;
            // 큰 것은 버리고, 작은 것을 취한다.
            preEnd = in[k][1] < preEnd ? in[k][1] : preEnd;
        }
        else preEnd = in[k][1];
    }
    return minRet;
}

 

 

잘 해결 되었다.