-
Notifications
You must be signed in to change notification settings - Fork 8
/
covering_segments.c
100 lines (90 loc) · 2.89 KB
/
covering_segments.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
* Author: Leandro Augusto Lacerda Campos <llacerdacampos@gmail.com>
*
* Data Structures and Algorithms Specialization,
* by University of California, San Diego,
* and National Research University Higher School of Economics
*
* Course 1: Algorithmic Toolbox
*
* Solution for Collecting Signatures Problem
*/
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
typedef struct interval
{
unsigned int a;
unsigned int b;
} interval;
int interval_comparison(const interval *, const interval *);
unsigned int intersection(interval, interval, interval *);
unsigned int optimal_points(const interval *, unsigned char, unsigned int *);
int main()
{
unsigned char n; /* number of intervals */
interval *intervals;
unsigned int *points;
unsigned int n_points;
unsigned char i;
scanf("%hhu", &n);
intervals = malloc(n * sizeof(interval));
points = malloc(n * sizeof(unsigned int));
for (i = 0; i < n; i++)
scanf("%u %u", &(intervals[i].a), &(intervals[i].b));
n_points = optimal_points(intervals, n, points);
printf("%u\n", n_points);
for (i = 0; i < n_points; i++)
printf("%u ", points[i]);
printf("\n");
free(intervals);
free(points);
return 0;
}
/*
* interval_comparison: return -1 if the lower end of i is smaller than the lower end of j;
* 0 if they are equal; and 1 if it is larger.
*/
int interval_comparison(const interval *i, const interval *j)
{
return i->a - j->a;
}
/*
* intersection: return the intersection between the intervals i and j, assuming that the
* lower end of i is smaller than or equal to the lower end of j.
*/
unsigned int intersection(interval i, interval j, interval *k)
{
if (i.b < j.a)
return 0;
k->a = j.a;
k->b = min(i.b, j.b);
return 1;
}
/*
* optimal_points: find a set of integers, points, of the minimum size such that, for any interval [a, b],
* there is a point x in points such that a <= x <= b. The return value of this function is the number of
* points x. The size of the array points has to be enough to contain all points x.
*/
unsigned int optimal_points(const interval *intervals, unsigned char nintervals, unsigned int *points)
{
const interval *current_interval, *next_interval, *last_interval;
unsigned int n_points;
interval k;
qsort((void *)intervals, nintervals, sizeof(interval),
(int (*)(const void *, const void *))interval_comparison);
current_interval = &intervals[0];
next_interval = current_interval + 1;
last_interval = &intervals[nintervals - 1];
n_points = 0;
while (current_interval <= last_interval)
{
k = *current_interval;
while (next_interval <= last_interval && intersection(k, *next_interval, &k))
next_interval++;
current_interval = next_interval++;
n_points++;
*points++ = k.b;
}
return n_points;
}