高效求解竖线穿过最多水平线段的最大相交数问题

给定若干由端点a到b表示的水平线段，例如(6 to 10)、(9 to 11)、(1, 20)，需要编写代码找到能够穿过最多水平线段的竖线，统计该竖线穿过的线段总数量。

对于如下给出的测试用例，答案为3，即存在竖线最多可穿过3条水平线段：

测试用例输入：

6 10
10 14
1 5
8 11
13 15
10 12
12 16
2 7

求该问题的高效求解方案。

• 暴力枚举坐标法：构建覆盖所有坐标范围的数组，遍历每条线段，对线段覆盖到的所有坐标对应数组位置计数+1，最后遍历数组取最大值。该方法时间、空间复杂度随坐标范围线性增长，坐标跨度大时效率极低，还容易因数组越界触发运行时错误。
• 端点排序差分法：将每条线段的左端点标记为+1（表示竖线过该点时新增穿过1条线段），右端点标记为-1（表示竖线过该点后减少1条穿过的线段），将所有端点按坐标排序后遍历，累加当前计数值，过程中记录的最大计数值即为结果。已编写实现代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int N, x, y, cnt, max_cnt = 0;
vector<pair<int, int>> end_points;

int main()
{
  cin >> N;

  for (int i = 0; i < N; i++) {
    cin >> x >> y;
    end_points.push_back(make_pair(x, 1));
    end_points.push_back(make_pair(y, -1));
  }

  sort(end_points.begin(), end_points.end());

  for (const auto &e : end_points)
  {
    cnt += e.second;
    max_cnt = max(max_cnt, cnt);
  }

  cout << max_cnt;
}

代码注意点：上述实现默认按pair的默认规则排序，坐标相同时会先处理值更小的标记（即先处理-1再处理+1）。如果题目定义线段为闭区间（竖线压在线段端点上也算穿过），则需要调整排序规则，保证坐标相同的情况下+1标记排在-1标记之前，否则会出现端点处计数少算的问题。

内容的提问来源于stack exchange，提问作者Hyunseung