HW3_requests

#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].finish <= a[r - 1].finish)
        {
            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;
    scanf("%d", &n);
    request* arr = (request*)malloc(n*sizeof(request));
    request t;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i].start);
        scanf("%d", &arr[i].finish);
    }

    qsort(arr, 0, n);
    t = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i].start > t.finish)
        {
            printf("%d %d\n", t.start, t.finish);
            t = arr[i];
        }
    }
    printf("%d %d\n", t.start, t.finish);
    return 0;
}