In this question I would like to ask you to hack/break my code because I can't think of any test cases it doesn't pass, however, it does not pass the grader.
So here's the problem description: a set of n segments [l, r] on the line, l <= r. We need to find the minimum number of points such that each segments has at least one point and print the set of such points. If there are multiple versions of the set, print any.
As you see, here we have points 'poking' segments, not segments covering maximum points (by that I want to say I did search and reading on the segments-cover-points problems but it didn't help).
1 <= n <= 100; 0 <= li <= ri <= 10^9, 0<= i <= n
So here's what I do:
So here's the code:
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned int point;
struct segment {
point l;
point r;
segment(point l1, point r1): l(l1), r(r1) {}
bool operator < (const segment &rhs) const { return r < rhs.r; }
};
int main(int argc, const char * argv[]) {
int nSegments = 0;
scanf("%d", &nSegments);
vector<segment> segments;
for(int i = 0; i < nSegments; i++) {
int l = 0, r = 0;
scanf("%d %d", &l, &r);
segments.push_back(segment(l, r));
}
sort(segments.begin(), segments.end());
vector<point> points;
point right = segments[0].r;
points.push_back(right);
for (int i = 1; i < nSegments; i++) {
if (segments[i].l < right) {
right = segments[i].r;
continue;
}
if (segments[i].l > points[points.size() - 1]) {
points.push_back(segments[i].r);
right = segments[i].r;
continue;
}
}
//for(int i = 0; i < nSegments; i++)
// printf("[%d %d]\n", segments[i].a, segments[i].b);
printf("%lu\n", points.size());
for (int i = 0; i < points.size(); i++) {
printf("%d ", points[i]);
}
return 0;
}
I've thought of any possible test case and it passes them, but can't see what's wrong with the algorithm.
PS I know it's not the best C++ code ever either, but now it's the problem itself that's bugging me.
Consider the following segments:
l0 r0
|-----| r1
|-------|
l1 |----|
l2 r2
Since each segment overlaps the previous, the algorithm will return the set {r0}
. If you remove Step 3, the algorithm returns a correct answer, {r0, r1}
.