c++ – Error in code: Access violation while reading

Question:

Task: Given n segments, it is necessary to find a set of points of 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 integers 0≤l≤r≤109, defining the beginning and end of the segment. Output the optimal number m of points and the m points themselves. If there are several such sets of points, print any of them.

My decision:

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;//двумерный массив отрезков
int N;
int M=2;
int *x;//одномерный массив точек

cout << "Enter N: "; //ввод количества отрезков
cin>>N;

x = new int[N]; //инициализация массива, который потом станет массивом точек
for (int i=0; i<N; i++)
    x[i]=0;

a = new int *[N];
for (int i = 0; i < N; i++)
    a[i] = new int [M];
//ввод концов отрезков    
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        cin >> a[i][j];
    }
}
//вывод до сортировки
cout <<endl << "Before sorting:" << endl;

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
        cout << std::setw(3) << a[i][j] << " ";
        cout << endl;
}


sort(a, N, M);//сортировка массива

//вывод после сортировки
cout << endl << "After sorting:" << endl;

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
        cout << setw(3) << a[i][j] << " ";

    cout << endl;
}
//вызов функции с жадным алгоритмом
greedy(a,x, N);

for (int i=0; i<=N; i++)
    cout<<x[i]<<' ';

system("pause");
return 0;
}


void swap(int *a1, int *a2, int M)//меняет 2 строки местами
{
for (int i = 0; i < M; i++)
{
    int temp = a1[i];
    a1[i] = a2[i];
    a2[i] = temp;
    }
}

void sort(int **a, int N, int M)//сортировка пузырьком отрезков по правой   точке 
{
for (int i = 0; i < N; i++)
    for (int j = N - 1; j > i; j--)
        if (a[j - 1][1] >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<=N)
{
    x[k]=a[i][1];
    i++;
    while ((x[k]>=a[i][0]) && (x[k]<=a[i][1]))
    {i++;}
    k++;
}

}

But the program crashes with an error: Access violation while reading. Can anyone see why?

Answer:

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

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

// N - размер, последний индекс N-1, поэтому строго меньше N
while (i<=N)

similarly here:

for (int i=0; i<=N; i++)

slightly different here:

// Думаете за пределами массива нули? 
// А кто обещает? 
// Там может быть любой мусор, поэтому убежать можно далеко. Проверяйте i тоже.
while ((x[k]>=a[i][0]) && (x[k]<=a[i][1]))
{i++;}

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

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

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