Greedy Schedule

sched.c

#include <stdio.h>
#include <stdlib.h>

#if defined(__clang__) || defined(__GNUC__)
  #define sort qsort_r
  #define SORT_COMPARE(name) int name(const void *a, const void *b, void *arg)
  typedef SORT_COMPARE(sort_cmp_f);
#elif defined(_MSC_VER)
  #define sort qsort_s
  #define SORT_COMPARE(name) int name(void *arg, const void *a, const void *b)
  typedef SORT_COMPARE(sort_cmp_f);
#endif

static SORT_COMPARE(sched_cmp)
{
    const int *p = (const int*)arg;
    const int ai = *((const int*)a);
    const int bi = *((const int*)b);
    return p[ai*2+1]-p[bi*2+1];   
}
static int
sched(int *s, const int *a, int cnt)
{
    int n = 0, i;
    if (cnt <= 0) return 0;
    for (i = 0; i < cnt; ++i) s[i] = i;
    sort(s, cnt, sizeof(int), sched_cmp, a);
  
    for (i = 1; i < cnt; ++i) {
        if (a[s[i]*2] >= a[s[n]*2+1])
            s[++n] = s[i];
    } return n+1;
}
int main(void)
{
    static const int inv[] = {0,6,1,4,3,5,3,8,4,7,5,9,6,10,8,11};
    static const int total = (sizeof(inv)/sizeof(inv[0])) / 2;
    
    int i, res[total];
    int cnt = sched(res, inv, total);
    for (i = 0; i < cnt; ++i)
        printf("%d\n", res[i]);
    return 0;
}