R3W1D.c

R3W1D.c

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

struct x {
    long long left;
    long long right;
};

int cmp(const void *a, const void *b)
{
    if (((struct x *)a)->right != ((struct x *)b)->right)
        return (((struct x *)a)->left - ((struct x *)b)->left);
    else
        return ((struct x *)a)->right != ((struct x *)b)->right;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--) {
        int m;
        scanf("%d", &m);
        int i;
        struct x data[50000];
        for (i = 0; i < m; i++) {
            scanf("%lld", &data[i].left);
            scanf("%lld", &data[i].right);
        }
        qsort(data, m, sizeof(struct x), cmp);
        long long start = data[0].left, end = data[0].right, sum = 0;
        if (m == 1) {
            printf("%lld\n", data[0].right - data[0].left);
            continue;
        }
        for (i = 1; i < m; i++) {
            if (data[i].left <= end && data[i].right > end)
                end = data[i].right;
            if (data[i].left > end) {
                sum += end - start;
                start = data[i].left;
                end = data[i].right;
            }
            if (i == m - 1)
                sum += end - start;
        }
        printf("%lld\n", sum);
    }
    return 0;
}