C programming Design, code, and test a C program to mergesort a set of intervals

Question

C programming

Design, code, and test a C program to mergesort a set of intervals of positive rational numbers. The first line of the input will be n, the number of intervals in the remaining n input lines. Each input interval will have four non-zero integer values: num_left den_left num_ right den_right. If num_left is positive, then the left end of the interval is closed at num_left/den_left, otherwise the left end of the interval is open at - num_left/den_left. Similarly, if num_right is positive, then the right end of the interval is closed at num_right/den_right, otherwise the right end of the interval is open at - num_right/den_right. den_left and den_right will always be positive, each fraction is in reduced form, and every interval includes at least one number. The input should be read from standard input (which will be one of 1. keyboard typing. 2. a shell redirect (

Explanation / Answer

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

struct rational
{
int num, denom;
};

struct Interval
{
struct rational s, e;
int sOpen, eOpen;
};

int compareRational(struct rational a, struct rational b) {
return a.num*b.denom > b.denom*b.num;
}

int mycomp (const void * a, const void * b)
{
struct Interval *intervalA = (struct Intervl *)a;
struct Interval *intervalB = (struct Interval *)b;
int res = compareRational(intervalA->s, intervalB->s);
if (res == 0) {
return intervalA->sOpen > intervalB->sOpen;
}
return res;
}

struct rational maxR(struct rational a, struct rational b) {
return compareRational(a, b) ? a: b;
}

struct rational minR(struct rational a, struct rational b) {
return !compareRational(a, b) ? a: b;
}

void mergeIntervals(struct Interval arr[], int n)
{
qsort(arr, n, sizeof(struct Interval), mycomp);

int index = 0;

int i;
for (i=0; i<n; i++)
{
if (index != 0 && !compareRational(arr[index-1].s, arr[i].e))
{
while (index != 0 && !compareRational(arr[index-1].s, arr[i].e))
{
arr[index-1].e = maxR(arr[index-1].e, arr[i].e);
arr[index-1].s = minR(arr[index-1].s, arr[i].s);
index--;
}
}
else
arr[index] = arr[i];

index++;
}

for (i = 0; i < index; i++)
{
printf("%d %d %d %d ", arr[i].sOpen*arr[i].s.num, arr[i].s.denom, arr[i].eOpen*arr[i].e.num, arr[i].e.denom);
}
}

int main()
{
int n;
scanf("%d", &n);
int i;
struct Interval arr[n];
for(i = 0; i < n; i++) {
int startN, startD, endN, endD;
scanf("%d%d%d%d", &startN, &startD, &endN, &endD);
struct rational start, end;

struct Interval interval;
if (startN < 0) {
interval.sOpen = -1;
}
else {
interval.sOpen = 1;
}
if (endN < 0) {
interval.eOpen = -1;
}
else {
interval.eOpen = 1;
}
start.num = abs(startN);
start.denom = startD;
end.num = abs(endN);
end.denom = endD;

interval.s = start;
interval.e = end;
arr[i] = interval;
}
mergeIntervals(arr, n);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.