Spajanje preklapajućih intervala

Data je lista intervala. Potrebno je spojiti sve intervale koji se preklapaju i ispisati uređenu listu nepoklapajućih intervala.

Koristiti strukturu za interval i dinamičko prosirivanje niza (realloc), kao i sortiranje (qsort).

Ulaz

Program se pokreće komandnom linijom:

./mergeint <putanja_do_fajla>

Ulazni fajl sadrži broj $N$ ($1 \leq N \leq 10^9$), zatim u $N$ redova vrednosti $l$ i $r$ koje predstavljaju intervale $[l, r]$.

Izlaz

Na standardni izlaz ispisati spojene intervale, po jedan u liniji, rastuće po levoj granici.

Greške:

Primer

intervali.txt

5
1 3
2 4
10 8
7 9
15 20

command line

./mergeint intervali.txt

stdout

1 4
7 10
15 20

Primer

command line

./mergeint

stderr

Error: Invalid number of arguments.

Primer

command line

./mergeint nepostojeci_fajl.txt

stderr

Error: Could not open file nepostojeci_fajl.txt

Rešenje

main.c

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

typedef struct {
	int l, r;
} Interval;

static int cmp_interval(const void *a, const void *b)
{
	const Interval *interval_a = a;
	const Interval *interval_b = b;

	if (interval_a->l != interval_b->l) {
		return interval_a->l - interval_b->l;
	}

	return interval_a->r - interval_b->r;
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		fprintf(stderr, "Error: Invalid number of arguments.\n");
		exit(EXIT_FAILURE);
	}

	FILE *file = fopen(argv[1], "r");
	if (!file) {
		fprintf(stderr, "Error: Could not open file %s\n", argv[1]);
		exit(EXIT_FAILURE);
	}

	size_t n;
	fscanf(file, "%zu", &n);

	Interval *arr = malloc(n * sizeof (Interval));
	if (arr == NULL) {
		fclose(file);
		exit(EXIT_FAILURE);
	}

	for (size_t i = 0; i < n; i++) {
		fscanf(file, "%d %d", &arr[i].l, &arr[i].r);
	}

	fclose(file);

	qsort(arr, n, sizeof (Interval), cmp_interval);

	size_t write_idx = 0;
	for (size_t i = 1; i < n; i++) {
		if (arr[i].l <= arr[write_idx].r) {
			if (arr[i].r > arr[write_idx].r) {
				arr[write_idx].r = arr[i].r;
			}
		} else {
			write_idx++;
			arr[write_idx] = arr[i];
		}
	}
	size_t merged = write_idx + 1;

	for (size_t i = 0; i < merged; i++) {
		printf("%d %d\n", arr[i].l, arr[i].r);
	}

	free(arr);

	exit(EXIT_SUCCESS);
}