Task. Given a set of π segments {[π0, π0], [π1, π1], . . . , [ππβ1, ππβ1]} with integer coordinates on a line, find the minimum number π of points such that each segment contains at least one point. That is, find a set of integers π of the minimum size such that for any segment [ππ, ππ] there is a point π₯ β π such that ππ β€ π₯ β€ ππ.
Input Format. The first line of the input contains the number π of segments. Each of the following π lines contains two integers ππ and ππ (separated by a space) defining the coordinates of endpoints of the π-th segment.
Constraints. 1 β€ π β€ 100; 0 β€ ππ β€ ππ β€ 109 for all 0 β€ π < π.
Output Format. Output the minimum number π of points on the first line and the integer coordinates of π points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not difficult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)
I have implemented a solution for this problem and tried stress testing on it. It works really well. But while submitting it to coursera, i am getting "unknown signal 11" Can anyone help me to tackle this ?
#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>
using std::vector;
struct Segment
{
int start, end;
};
bool compareByStart(const Segment &a, const Segment &b)
{
return a.start < b.start;
}
vector<int> optimal_points(vector<Segment> &segments)
{
vector<int> points;
sort(segments.begin(), segments.end(), compareByStart);
for (long i = 0; i < segments.size(); ++i)
{
int temp=i;
int min=segments[i].end;
while(segments[i].start<=segments[temp].end && i<segments.size())
{
if(segments[i].end<min)
{
min=segments[i].end;
}
i++;
}
points.push_back(min);
i=temp;
while(segments[i+1].start<=min)
{
i++;
}
}
return points;
}
int main() {
int n;
std::cin >> n;
vector<Segment> segments(n);
for (size_t i = 0; i < segments.size(); ++i) {
std::cin >> segments[i].start >> segments[i].end;
}
vector<int> points = optimal_points(segments);
std::cout << points.size() << "\n";
for (size_t i = 0; i < points.size(); ++i) {
std::cout << points[i] << " ";
}
}
This is wrong:
while(segments[i].start<=segments[temp].end && i<segments.size())
You should check the index before you use it to acces an element not afterwards:
while(i < semgents.size() && segments[i].start<=segments[temp].end)
Later you have a loop that looks a bit scary, because you do not check the index at all:
while(segments[i+1].start<=min)
{
i++;
}
This can easily access segments
out-of-bounds as well.