[C] LeetCode 2406. Divide Intervals into Minimum Number of Groups

 

문제

번역

2차원 정수 배열 intervals가 주어진다. intervals의 각 원소는 \( [ left_i, right_i ] \) 로 구성된다.

이 intervals를 하나 이상의 그룹으로 나눠서 각 그룹마다 교집합이 없게 만들어야 한다.

이때 우리가 만들 수 있는 최소한의 그룹의 수를 반환해라

[1, 5] , [5, 8] 과 같이 하나의 수라도 겹치면 겹친다고 판단한다.

접근 방법과 소스코드

특정 시점에 동시에 겹치는 구간의 최대 개수를 구하면 된다.

어떤 interval의 시작시간이 다른 interval의 끝나는 시간보다 크면 어떤 구간이 끝난 것이므로 그룹을 재사용할 수 있다.

그게 아니라면 새로운 그룹이 필요한 경우이다.

 

이를 해결하기 위해 시작 시간과 끝나는 시간을 각각 정렬한 뒤 투포인터를 통해서 문제를 풀 수 있다.

int start[100001];
int   end[100001];

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int minGroups(int** intervals, int intervalsSize, int* intervalsColSize) {
    for(int i=0;i<intervalsSize;i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }

    qsort(start, intervalsSize, sizeof(int), compare);
    qsort(end  , intervalsSize, sizeof(int), compare);

    int groups=0;
    int endptr=0;
    for(int i=0;i<intervalsSize; i++) {
        if(start[i] > end[endptr]) {
            groups--;
            endptr++;
        }
        groups++;
    }
    return groups;
}

 

또 다른 풀이 방법도 있다. 이 문제는 대표적인 그리디 문제이다. minheap을 써서 이 문제를 풀 수 있다.

새 구간을 배정할때 가장 빨리 끝나는 그룹에 넣는 방식이다. 그게 불가능하면 새로운 그룹을 만들면 된다.

 

시작일 기준으로 전부 정렬을 한다.

가장 빨리 끝나는 그룹을 선택하되, 그 그룹이 현재 구간보다 먼저 끝난다면 재활용을 한다.

그게 아니라면 새로운 그룹을 만들어야 한다.

 

코드는 다음과 같다.

int heap[100001];
int rsp = 0;

void swap(int* a, int* b) { int t=*a; *a=*b; *b=t; }

void push(int x) {
    heap[++rsp] = x;
    int ch = rsp, pa = rsp/2;
    while(ch > 1 && heap[pa] > heap[ch]) { 
        swap(&heap[pa], &heap[ch]);
        ch = pa; pa = ch/2;
    }
}

int pop() {
    int r = heap[1];
    swap(&heap[1], &heap[rsp]); rsp--;
    int pa = 1, ch = 2;
    ch = (ch+1 <= rsp && heap[ch] > heap[ch+1]) ? ch+1 : ch;
    while(ch <= rsp && heap[pa] > heap[ch]) {
        swap(&heap[pa], &heap[ch]);
        pa = ch; ch = 2*pa;
        ch = (ch+1 <= rsp && heap[ch] > heap[ch+1]) ? ch+1 : ch;
    }
    return r;
}

int compare(const void* a, const void* b) {
    int* A = *(int**)a, *B = *(int**)b;
    return A[0] - B[0];
}

int minGroups(int** intervals, int intervalsSize, int* intervalsColSize) {
    rsp = 0;
    qsort(intervals, intervalsSize, sizeof(int*), compare);

    for(int i = 0; i < intervalsSize; i++) {
        if(rsp > 0 && heap[1] < intervals[i][0])
            pop();

        push(intervals[i][1]);
    }

    return rsp;
}

 

결과 차이는 크게 안나는 것 같다.