Search code examples
c++algorithmcoursera-api

Code works well on my computer but I am getting unknown signal 11 problem while submitting it to coursera


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] << " ";
  }
}

Solution

  • 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.