坐标轴区间选点算法问题求助：求最小选点数量

问题描述：在坐标系横轴上有多组区间，若在某区间内选取一个点，该区间会被简化为该点。给定X组区间，求需选取的最少点数量，使所有区间都被这些点覆盖。
输入规格：

• 输入1：区间组数X
• 输入2：包含X个区间的数组，每个区间由起始点和终点组成
  输出规格：返回符合要求的最少点数量
  示例1：
  输入1：3
  输入2：[{1,3}, {2,5}, {3,6}]
  输出：1
  示例2：
  输入1：3
  输入2：[{1,3}, {2,5}, {6,9}]
  输出：2

这是经典的区间贪心问题，最优解法是通过贪心策略实现，核心思路是用最少的点覆盖最多的区间，具体步骤如下：

核心贪心策略 #

1. 排序区间：将所有区间按右端点从小到大排序。这一步是关键，因为选择区间的右端点作为覆盖点，能最大程度覆盖后续可能重叠的区间。
2. 初始选点：从排序后的第一个区间的右端点开始选第一个点，计数初始化为1。
3. 遍历覆盖：依次检查后续每个区间：
   • 如果当前区间的左端点大于已选的最后一个点，说明该区间未被覆盖，需在其右端点新增一个点，计数加1。
   • 如果当前区间的左端点小于等于已选的最后一个点，说明该区间已被覆盖，直接跳过。

示例验证 #

示例1

输入区间排序后为：[{1,3}, {2,5}, {3,6}]

• 选第一个点：3（第一个区间的右端点）
• 第二个区间[2,5]的左端点2 ≤ 3，被覆盖；第三个区间[3,6]的左端点3 ≤ 3，被覆盖。最终只需1个点。

示例2

输入区间排序后为：[{1,3}, {2,5}, {6,9}]

• 选第一个点：3，覆盖前两个区间
• 第三个区间[6,9]的左端点6 > 3，新增点9，计数变为2。

代码实现（Python） #

def min_points(X, intervals):
    if X == 0:
        return 0
    # 按区间右端点升序排序
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    count = 1
    last_selected = sorted_intervals[0][1]
    for start, end in sorted_intervals[1:]:
        if start > last_selected:
            count += 1
            last_selected = end
    return count

# 测试示例1
print(min_points(3, [[1, 3], [2, 5], [3, 6]]))  # 输出: 1
# 测试示例2
print(min_points(3, [[1, 3], [2, 5], [6, 9]]))  # 输出: 2

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