HW3_segments

#include <cstdio>
#include <cstdlib>
#include <cassert>

struct request
{
    int start;
    int finish;
};

void swap(request &a, request &b)
{
    request t = a;
    a = b;
    b = t;
}

int partition(request* a, int l, int r)
{
    int i = l - 1;
    for (int j = l; j < r - 1; ++j)
    {
        if (a[j].start <= a[r - 1].start)
        {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[r - 1]);
    return i + 1;
}

void qsort(request* a, int l, int r)
{
    if (l >= r)
        return;
    int q = partition(a, l, r);
    qsort(a, l, q);
    qsort(a, q + 1, r);
}

int main()
{
    int n = 0, j = 0, k = 0;
    scanf("%d", &n);
    request* arr = (request*)malloc(n*sizeof(request));

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i].start);
        scanf("%d", &arr[i].finish);
    }

    qsort(arr, 0, n);
    request t = arr[0];
    printf("%d %d\n", t.start, t.finish);
    while (t.finish < 10000)
    {
        for (int i = j; arr[i].start < t.finish; i++)
        {
            if (arr[i].finish > k)
            {
                j = i;
                k = arr[i].finish;
            }
        }
        if (arr[j].start == t.start && arr[j].finish == arr[j].finish)
        {
            printf("NO\n");
            break;
        }
        t = arr[j];
        printf("%d %d\n", t.start, t.finish);
    }

    return 0;
}