[C] LeetCode 1353. Maximum Number of Events That Can Be Attended

문제

번역

events 배열이 주어지고 events 배열의 각 원소는 [startDay_i, endDay_i]로 이루어져 있다.

각 이벤트 i 는 startDay_i 날에 시작해서 endDay_i 날에 끝난다.

우리는 이벤트가 열리는 날 중 하루만 참석할 수 있다. 이벤트는 하루에 한번만 참여할 수 있다.

우리가 참석 가능한 이벤트의 최대 개수를 반환해라.

 

접근 방법과 소스코드

그리디와 MinHeap을 써서 오늘 참석 가능한 이벤트 중 가장 빨리 끝나는 이벤트에 참석하면 된다.

늦게 끝나는 이벤트는 나중에 참석할 수 있기에 빨리 끝나는 이벤트를 우선해서 고른다.

 

오늘 시작하는 이벤트를 MinHeap에 전부 넣는다. 

그리고 오늘 이전에 끝난, 즉 내가 더이상 참석하지 못하는 이벤트는 전부 날린다.

그 중 가장 빨리 끝나는, MinHeap의 root에 있는 이벤트를 꺼내면 된다.

 

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;
    int ch = 2*pa;
    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;
    int* B = *(int**)b;
    if(A[0] == B[0]) return A[1]-B[1];
    else return A[0]-B[0];
}

int maxEvents(int** events, int eventsSize, int* eventsColSize) {
    rsp = 0;
    qsort(events, eventsSize, sizeof(int*), compare);
    int counter = 0, curday=-1, i=0;
    while(i < eventsSize || rsp > 0) {
        if(rsp == 0) {
            curday = events[i][0];
        }
        while(i < eventsSize && curday == events[i][0]) push(events[i++][1]);
        while(rsp > 0 && heap[1] < curday) pop();
        if(rsp > 0) { counter++; pop(); }
        curday++;
    }
    return counter;
}