如何用C#计算0到指定数值中未被区间覆盖的数字总数

需求说明 #

• 统计0到指定数值（示例为100）范围内，未被给定区间覆盖的数字总数。
• 输入规则：
  • 第一行输入两个整数：数值范围上限、区间数量。
  • 后续每行输入一个区间的起止整数。
• 示例：输入上限100、区间数5，5个区间后，输出结果为65。

用户提供的部分代码 #

static void Main(string[] args)
{
    string input1 = Console.ReadLine();
    int roadlength = Convert.ToInt32(input1.Split(" ")[0]);
    int stagecnt = Convert.ToInt32(input1.Split(" ")[1]);
    int[] startpoint = new int[stagecnt];
    int[] endpoint = new int[stagecnt];
    int km = 0;

    for (int i = 0; i < stagecnt; i++)
    {
        string input2 = Console.ReadLine();
        startpoint[i] = Convert.ToInt32(input2.Split(' ')[0]);
        endpoint[i] = Convert.ToInt32(input2.Split(' ')[1]);
        
    }
    for (int i = 0; i < stagecnt; i++)
    {

完整实现代码 #

核心思路是先合并重叠/相邻区间，避免重复计算覆盖长度，再用总数字数减去覆盖数得到结果。完整代码如下：

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        string input1 = Console.ReadLine();
        int roadlength = Convert.ToInt32(input1.Split(" ")[0]);
        int stagecnt = Convert.ToInt32(input1.Split(" ")[1]);
        List<Tuple<int, int>> intervals = new List<Tuple<int, int>>();

        for (int i = 0; i < stagecnt; i++)
        {
            string input2 = Console.ReadLine();
            string[] parts = input2.Split(' ');
            int start = Convert.ToInt32(parts[0]);
            int end = Convert.ToInt32(parts[1]);
            // 修正区间起止顺序，处理输入逆序情况
            if (start > end)
            {
                (start, end) = (end, start);
            }
            // 限制区间在0到roadlength的有效范围内
            start = Math.Max(start, 0);
            end = Math.Min(end, roadlength);
            intervals.Add(Tuple.Create(start, end));
        }

        // 无区间时直接输出总数字数
        if (intervals.Count == 0)
        {
            Console.WriteLine(roadlength + 1);
            return;
        }

        // 按区间起点排序，方便合并操作
        intervals.Sort((a, b) => a.Item1.CompareTo(b.Item1));

        // 合并重叠/相邻区间
        List<Tuple<int, int>> mergedIntervals = new List<Tuple<int, int>> { intervals[0] };
        for (int i = 1; i < intervals.Count; i++)
        {
            var lastMerged = mergedIntervals[mergedIntervals.Count - 1];
            var current = intervals[i];
            // 当前区间与最后一个合并区间重叠或相邻，则合并
            if (current.Item1 <= lastMerged.Item2 + 1)
            {
                int newEnd = Math.Max(lastMerged.Item2, current.Item2);
                mergedIntervals[mergedIntervals.Count - 1] = Tuple.Create(lastMerged.Item1, newEnd);
            }
            else
            {
                mergedIntervals.Add(current);
            }
        }

        // 计算覆盖的总数字数
        int coveredCount = 0;
        foreach (var interval in mergedIntervals)
        {
            coveredCount += interval.Item2 - interval.Item1 + 1;
        }

        // 总数字数为roadlength+1（包含0和roadlength），减去覆盖数得到未覆盖数
        int uncoveredCount = (roadlength + 1) - coveredCount;
        Console.WriteLine(uncoveredCount);
    }
}

代码说明 #

1. 输入处理：读取输入并修正区间起止顺序，同时过滤掉超出0到roadlength的无效区间部分。
2. 区间排序：按区间起点从小到大排序，为后续合并操作做准备。
3. 区间合并：遍历排序后的区间，将重叠或相邻的区间合并为一个大区间，避免重复计算覆盖长度。
4. 结果计算：先统计所有合并后区间覆盖的数字总数，再用总数字数减去覆盖数，得到未被覆盖的数字数量。

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