程序超时求助：病毒致死温度最小区间算法优化

我是第一次提问，还请多包涵。我正在解决一个算法问题，当前程序无法通过时间限制，尝试用ArraySegment优化区间检查但没成功，希望能得到优化思路。

问题详情 #

• 时间限制：1秒，内存限制：256 MiB
• 问题描述：病毒学家对K种病毒毒株做实验，记录了每种毒株的致死温度（每种毒株实验次数不同）。定义对所有毒株都致命的温度区间为包含至少每种毒株一个致死温度的区间，区间大小为边界差值。需要找出该区间的最小可能大小。

输入格式 #

• 第一行输入正整数K（病毒毒株数量，1≤K≤10^5）
• 随后K行，每行第一个数为第i种毒株的实验次数Mi（1<Mi≤10^{5），后续为Mi个该毒株的致死温度值（范围-10}7到10^{7），所有实验总次数不超过10}5。

输出格式 #

输出一个整数，表示最小的温度区间大小。

示例 #

测试输入：
3
5 3 9 15 24 20
4 1 9 13 14
4 5 15 12 11
输出：1

现有代码 #

using System;
using System.Collections.Generic;
using System.Linq;

namespace SkuratovAvtomat
{
    internal class Program
    {
        public static void Main()
        {
            int gr1, gr2;
            int min = Int32.MaxValue;
            int kount = Convert.ToInt32(Console.ReadLine());
            int j;
            int[][] virus = new int[kount][];
            List<int> temp = new List<int>();
            
            for (int i = 0; i < kount; i++)
            {
                List<int> tempp = new List<int>();
                int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                virus[i] = input;
                tempp.AddRange(virus[i]);
                tempp.RemoveRange(0,1);
                temp.AddRange(tempp);
            }

            SortedSet<int> sorttemp = new SortedSet<int>(temp);
            temp.Clear();
            temp = sorttemp.ToList();
            int y = temp.Count;
            for (int i = 0; i < y; i++)
             {
                 
                 gr1 = temp[i];
                 for (int k = i; k < y; k++)
                 {
                     j = 0;
                     gr2 = temp[k];
                     
                     for (int o = 0; o < kount; o++)
                     {
                         bool prov = false;
                         for (int l = 1; l < virus[o].Length; l++)
                         {
                             if (gr1 <= virus[o][l] & virus[o][l] <= gr2)
                             {
                                 j++;
                                 prov = true;
                                 break;
                             }
                         }
                         if (prov == false)
                             break;
                     }
                     if(j == kount)
                         min = Math.Min(Math.Abs(gr1 - gr2), min);
                 }
             }
             Console.WriteLine(min);
        }
    }
}

问题分析与优化思路 #

现有代码采用三重循环，时间复杂度为O(N²*K)（N为去重后的温度数量），当数据量接近上限时必然超时。以下是可行的优化方案：

核心优化方向 #

1. 排序+二分查找：先对每种病毒的温度数组排序，之后可以用二分查找快速判断某个区间是否包含该病毒的温度，将单病毒检查的时间从O(Mi)降到O(logMi)。
2. 滑动窗口（双指针）：将所有温度带上病毒标记后排序，用双指针维护一个包含所有K种病毒的窗口，动态调整窗口大小以找到最小区间，时间复杂度可降至O(T log T)（T为总实验次数）。

具体实现步骤（滑动窗口方案） #

1. 预处理每个病毒的温度数组：对每个毒株的温度列表进行排序，方便后续处理。
2. 构建带标记的温度列表：将所有温度与其所属毒株的索引绑定，形成(温度值, 毒株索引)的结构体，然后按温度值从小到大排序。
3. 滑动窗口遍历：
   • 用两个指针left和right表示当前窗口的左右边界，维护一个计数器count记录窗口内包含的不同毒株数量，以及一个数组virusCount统计每个毒株在窗口内出现的次数。
   • 移动right指针扩展窗口，直到count等于K（窗口包含所有毒株）。
   • 此时尝试移动left指针缩小窗口，同时更新最小区间大小，直到窗口不再包含所有毒株，重复此过程直至遍历结束。

优化后代码示例 #

using System;
using System.Collections.Generic;
using System.Linq;

namespace SkuratovAvtomat
{
    internal class Program
    {
        public static void Main()
        {
            int k = int.Parse(Console.ReadLine());
            var virusTemperatures = new List<List<int>>();
            
            // 读取并排序每个毒株的温度列表
            for (int i = 0; i < k; i++)
            {
                var parts = Console.ReadLine().Split().Select(int.Parse).ToArray();
                var temps = parts[1..].ToList();
                temps.Sort();
                virusTemperatures.Add(temps);
            }

            // 构建所有带标记的温度列表
            var allTemps = new List<(int Temp, int VirusIdx)>();
            for (int i = 0; i < k; i++)
            {
                foreach (var temp in virusTemperatures[i])
                {
                    allTemps.Add((temp, i));
                }
            }

            // 按温度排序
            allTemps.Sort((a, b) => a.Temp.CompareTo(b.Temp));

            int minInterval = int.MaxValue;
            int left = 0;
            int uniqueViruses = 0;
            var virusCount = new int[k]; // 统计每个毒株在窗口内的出现次数

            for (int right = 0; right < allTemps.Count; right++)
            {
                var (temp, idx) = allTemps[right];
                if (virusCount[idx] == 0)
                {
                    uniqueViruses++;
                }
                virusCount[idx]++;

                // 当窗口包含所有毒株时，尝试缩小左边界
                while (uniqueViruses == k)
                {
                    int currentInterval = allTemps[right].Temp - allTemps[left].Temp;
                    if (currentInterval < minInterval)
                    {
                        minInterval = currentInterval;
                    }

                    var leftTempInfo = allTemps[left];
                    virusCount[leftTempInfo.VirusIdx]--;
                    if (virusCount[leftTempInfo.VirusIdx] == 0)
                    {
                        uniqueViruses--;
                    }
                    left++;
                }
            }

            Console.WriteLine(minInterval);
        }
    }
}

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