Problem: Given n segments, it is necessary to find a set of points of the minimum size for which each of the segments contains at least one of the points.

The first line contains the number 1≤n≤100 segments. Each of the next n lines contains two numbers 0≤l≤r≤109, specifying the beginning and end of the segment. Print the optimal number of m points and the m points themselves. If there are several such sets of points, print any of them.

My solution:

void swap (int * a1, int * a2, int M);
void sort (int ** a, int N, int M);
void greedy (int ** a, int * x, int N);
int main ()
{
int ** a; // two-dimensional array of segments
int N;
int M = 2;
int * x; // one-dimensional array of points
cout & lt; & lt; "Enter N:"; // enter the number of segments
cin & gt; & gt; N;
x = new int [N]; // initialize an array, which will later become an array of points
for (int i = 0; i & lt; N; i ++)
  x [i] = 0;
a = new int * [N];
for (int i = 0; i & lt; N; i ++)
  a [i] = new int [M];
// enter the ends of the segments
for (int i = 0; i & lt; N; i ++)
{
  for (int j = 0; j & lt; M; j ++)
  {
    cin & gt; & gt; a [i] [j];
  }
}
// output before sorting
cout & lt; & lt; endl & lt; & lt; "Before sorting:" & lt; & lt; endl;
for (int i = 0; i & lt; N; i ++)
{
  for (int j = 0; j & lt; M; j ++)
    cout & lt; & lt; std :: setw (3) & lt; & lt; a [i] [j] & lt; & lt; "";
    cout & lt; & lt; endl;
}
sort (a, N, M); // sort the array
// output after sorting
cout & lt; & lt; endl & lt; & lt; "After sorting:" & lt; & lt; endl;
for (int i = 0; i & lt; N; i ++)
{
  for (int j = 0; j & lt; M; j ++)
    cout & lt; & lt; setw (3) & lt; & lt; a [i] [j] & lt; & lt; "";
  cout & lt; & lt; endl;
}
// call a function with a greedy algorithm
greedy (a, x, N);
for (int i = 0; i & lt; = N; i ++)
  cout & lt; & lt; x [i] & lt; & lt; ' ';
system ("pause");
return 0;
}
void swap (int * a1, int * a2, int M) // swaps 2 lines
{
for (int i = 0; i & lt; M; i ++)
{
  int temp = a1 [i];
  a1 [i] = a2 [i];
  a2 [i] = temp;
  }
}
void sort (int ** a, int N, int M) // bubble sorting of segments by the right point
{
for (int i = 0; i & lt; N; i ++)
  for (int j = N - 1; j & gt; i; j--)
    if (a [j - 1] [1] & gt; a [j] [1])
      swap (a [j - 1], a [j], M);
}
void greedy (int ** a, int * x, int N)
{
int i = 0;
int k = 0;
while (i & lt; = N)
{
  x [k] = a [i] [1];
  i ++;
  while ((x [k] & gt; = a [i] [0]) & amp; & amp; (x [k] & lt; = a [i] [1]))
  {i ++;}
  k ++;
}
}

But the program crashes with an error: Read access violation. Maybe someone sees why?

Answer 1, authority 100%

Again tasks from the stepik from the Algorithms course. Guys, you are learning for yourself, try to figure it out for yourself.

The crux of the problem is obvious: you ran out of the array. I see three places where this happens:

// N is the size, the last index is N-1, therefore strictly less than N
while (i & lt; = N)

is similar here:

for (int i = 0; i & lt; = N; i ++)

here a little differently:

// Thinking outside the array of zeros?
// And who promises?
// Any trash can be there, so you can run far. Check i too.
while ((x [k] & gt; = a [i] [0]) & amp; & amp; (x [k] & lt; = a [i] [1]))
{i ++;}

Well, return from greedy k to find out the number of points.

And yes, I recommend making a structure with two fields for a segment: you will not bother with a two-dimensional array, the code will become more readable, and as a result, it is easier to look for errors in such code. And also give meaningful names to variables. What prevents x from being named dots or points , and a – lines , I already I’m not talking about the passionate desire for manual memory management, instead of std :: vector .

Well, learn how to use debuggers and profilers like Valgrind, they will almost poke you where you have an error.

Answer 2, authority 25%

You are out of range when i = N, correct in & lt; = loops to & lt ;.

Answer 3

cout , cin , system ("pause") work with the external environment – if the problem is with them, comment out the calls.

But it looks more like an error somewhere in the sizes of arrays and accessing an element outside of them.

I recommend that you use the debugger and publish all error details.