是否有一种算法可以检查一系列范围是否形成一个连续范围？

Question

我正在寻找一种算法来检查输入的随机浮点范围选择是否形成一个连续范围，并返回完整的连续范围或其覆盖的范围。

例如，假设有人输入以下内容：

[16.0f, 40.0f], [30.0f, 55.0f], [1.0f, 25.0f]

我需要算法表明它是连续的并返回

[1.0f, 55.0f]

。

但是，如果有人输入：

[10.0f, 25.0f], [5.0f, 9.0f], [1.0f, 7.0f], [20.0f, 34.0f]

我需要算法表明它不是连续范围并返回

[1.0f, 9.0f], [10.0f, 34.0f]

。

我目前所做的事情是：

for (int i = 0; i < InIntervalRanges.num(); ++i)
{
    const Interval CurrentRange = InIntervalRanges[i];

    bool bAddedToRange = false;
    for (Interval& AllowedHeight : OutIntervalRanges)
    {
        if (AllowedHeight.Contains(CurrentRange.Min))
        {
            AllowedHeight.Include(CurrentRange.Max);
            bAddedToRange = true;
            break;
        }
        if (AllowedHeight.Contains(CurrentRange.Max))
        {
            AllowedHeight.Include(CurrentRange.Min);
            bAddedToRange = true;
            break;
        }
    }

    if (!bAddedToRange)
    {
        OutIntervalRanges.Add(CurrentRange);
    }
}

if (OutIntervalRanges.Num() > 1)
{
    return false;
}

return true;

其中

Interval

具有

Min

和

Max

，

Contains

检查某个值是否在间隔范围内，并且

Include

扩展间隔范围以包含尚未在间隔范围内的值。范围。

有没有更有效的算法？我并不期望有大量的间隔，但我想知道是否有更有效的方法来做到这一点？

编辑：添加了尝试的解决方案。

Answer 1

我不确定您是否仍然遇到问题，但我在创建可用性议程时遇到了同样的问题。

我决定创建一个“连续体”类来表示完整的数字或时间线。 （仅限子集）

这就是我最终的结果：

    public class Continuum<TItem> : IReadOnlyList<(TItem Start, TItem End)>
        where TItem : IComparable, IComparable<TItem>, IEquatable<TItem>
    {
        private readonly List<(TItem Start, TItem End)> intervals = new();

        public Continuum(TItem minValue, TItem maxValue)
        {
            MinValue = minValue;
            MaxValue = maxValue;
        }

        /// <summary>
        /// The lower bound of the continuum.
        /// Ranges are clipped to this value.
        /// </summary>
        public TItem MinValue { get; }

        /// <summary>
        /// The upper bound of the continuum.
        /// Ranges are clipped to this value.
        /// </summary>
        public TItem MaxValue { get; }

        /// <summary>
        /// Modifies a range in the continuum.
        /// </summary>
        public void Modify(TItem start, TItem end, bool enabled)
        {
            if (enabled) Add(start, end);
            else Remove(start, end);
        }

        /// <summary>
        /// Adds a range to the continuum. 
        /// If the range overlaps with existing ranges, they are merged.
        /// If the range is out of bound, it is clipped or ignored.
        /// </summary>
        public void Add(TItem start, TItem end)
        {
            if (!TryFixRange(ref start, ref end)) return;
            (var index, var overlapCount) = FindIndex(start, end);
            if (overlapCount > 0)
            {
                if (intervals[index].Start.CompareTo(start) < 0) start = intervals[index].Start;
                if (intervals[index + overlapCount - 1].End.CompareTo(end) > 0) end = intervals[index].End;
                intervals.RemoveRange(index, overlapCount);
            }
            intervals.Insert(index, (start, end));
        }

        /// <summary>
        /// Removes a range from the continuum. 
        /// Existing ranges are partially or completely removed.
        /// If the range is out of bound, it is clipped or ignored.
        /// </summary>
        public void Remove(TItem start, TItem end)
        {
            if (!TryFixRange(ref start, ref end)) return;
            (var index, var overlapCount) = FindIndex(start, end);
            if (overlapCount == 0) return;
            var startOfFirstIntervalToClip = intervals[index].Start;
            var endOfLastIntervalToClip = intervals[index + overlapCount - 1].End;
            intervals.RemoveRange(index, overlapCount);
            if (endOfLastIntervalToClip.CompareTo(end) > 0) intervals.Insert(index, (end, endOfLastIntervalToClip));
            if (startOfFirstIntervalToClip.CompareTo(start) < 0) intervals.Insert(index, (startOfFirstIntervalToClip, start));
        }

        /// <summary>
        /// Tries to fix a range by clipping it to the bounds of the continuum.
        /// </summary>
        private bool TryFixRange(ref TItem start, ref TItem end)
        {
            if (start.CompareTo(end) >= 0 || start.CompareTo(MaxValue) >= 0 || end.CompareTo(MinValue) <= 0) return false;
            if (MinValue.CompareTo(start) > 0) start = MinValue;
            if (MaxValue.CompareTo(end) < 0) end = MaxValue;
            return true;
        }

        /// <summary>
        /// Find the index where to insert or delete the range, 
        /// plus the number of existing adjacent ranges that overlap with the range.
        /// </summary>
        private (int index, int overlapCount) FindIndex(TItem start, TItem end)
        {
            var i = 0;
            while (i < intervals.Count && intervals[i].End.CompareTo(start) < 0) i++;
            var c = 0;
            while (i + c < intervals.Count && intervals[i + c].Start.CompareTo(end) <= 0) c++;
            return (i, c);
        }

        /// <inheritdoc/>
        public int Count => intervals.Count;
        /// <inheritdoc/>
        public (TItem Start, TItem End) this[int index] => intervals[index];
        /// <inheritdoc/>
        public IEnumerator<(TItem Start, TItem End)> GetEnumerator() => intervals.GetEnumerator();
        /// <inheritdoc/>
        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

        /// <summary>
        /// Determines the enabled state at a given point in the continuum.
        /// </summary>
        public bool this[TItem key] => intervals.Exists(i => i.Start.CompareTo(key) <= 0 && i.End.CompareTo(key) > 0);

        /// <summary>
        /// Clips the continuum to the given range.
        /// </summary>
        public void Clip(TItem start, TItem end)
        {
            Remove(MinValue, start);
            Remove(end, MaxValue);
        }
    }