Problem

Horizontal lines such as (6 to 10), (9 to 11), (1, 20) which is point a to b are given and code should find a line that crosses maximum number of horizontal lines.

So, the following lines below, the answer is 3 because the maximum number a vertical line can be made goes through 3 lines.

Example

Any suggestions for how to solve this problem efficiently?

What I have tried

I have tried making an array and increasing the value of it by iterating through the line's starting point to the end. This way, the maximum number can be detected. Runtime error and the code is slow.

#include <iostream>
using namespace std;

int N, x, y, maxv = 0, grid[1000001] = {0};

int main()
{
  cin >> N;

  for (int i = 0; i < N; i  )
  {
    cin >> x >> y;

    for (int j = x; j < y; j  )
      grid[j]  ;
  }

  for (int i = 0; i < 1000001; i  )
    maxv = max(maxv, grid[i]);

  cout << maxv;
}

CodePudding user response：

Max value can be updated while incrementing the grid value in the first for loop.

When incrementing the array values j < y should be updated as j < (y 1) since you have to increment grid[y] value too.

The answer for your example should be 4. At point 10, a vertical line will be intersected at 4 points.

int N, x, y, maxv = 0, grid[1000001] = {0};

int main()
{
  cin >> N;

  for (int i = 0; i < N; i  )
  {
    cin >> x >> y;
    
    for (int j = x; j < (y   1); j  )
    {
      grid[j]  ;
      maxv = max(maxv, grid[j]);
    }
  }
  
  /*for (int i = 0; i < 1000001; i  )
    maxv = max(maxv, grid[i]);*/

  cout << maxv;
}

CodePudding user response：

Consider the example of two intervals

 0 1000000
 42 44

You don't need a loop from 0 till 1000000 to find that 43 is inside both intervals.

You only need to consider the end points of the intervalls. When they are sorted they are 0,42,44,1000000. Then loop those end points. When the end point is the start of an interval you increment the count when it is the end of an interval you decrement the count. Thats 4 iterations instead of 1000000.

The following assumes that there is no overlap between intervals that have an end point in common, eg with two intervals (0,10) and (10,20) there is no point with count 2 (ie the intervals are open, for closed intervals only a small modification is necessary).

#include <sstream>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>

int main()
{
    std::istringstream input {"6 10 \
                              10 14 \
                               1  5 \
                               8 11 \
                              13 15 \
                              10 12 \
                              12 16 \
                              2 7"};

    std::vector<std::pair<int,int>> end_points;
    int sta,sto;
    while (input >> sta >> sto) {
        end_points.push_back({sta,1});
        end_points.push_back({sto,-1});
    }

    std::sort(end_points.begin(),end_points.end());
    int count = 0;
    int max_count = 0;
    for (const auto& e : end_points) {
        count  = e.second;
        max_count = std::max(max_count,count);
    }
    std::cout << max_count;
}