c# - 在 C# 中合并间隔与合并距离

Question

给定一个区间列表 [start, end] 我必须根据指定的合并距离合并它们。间隔以特定顺序到达，并且当它们到达时，它应该在收到每个间隔时根据指定的合并距离合并它们。其中一些间隔将被删除（在到达流中它们将被标记为已删除）——在这种情况下，我必须将原始间隔视为从未存在过。例子：

合并距离为 7 - 在以下示例中，输入按顺序到达

我尝试了以下算法来合并它们，但我的输出不像上面的例子。有人可以帮助我吗，我在这里缺少什么！

这是我的代码。

class Program
    {
        static void Main(string[] args)
        {
            var intervals = new List<Interval>
            {
                new Interval
                {
                    start = 1,
                    end = 20
                },
                new Interval
                {
                    start = 55,
                    end = 58
                },
                new Interval
                {
                    start = 60,
                    end = 89
                },
                new Interval
                {
                    start = 15,
                    end = 31
                },
                new Interval
                {
                    start = 10,
                    end = 15
                },
                new Interval
                {
                    start = 1,
                    end = 20
                }
            };

            var mergedIntervals = Merge(intervals, 7);

            foreach (var item in mergedIntervals)
            {
                Console.WriteLine($"[{item.start}, {item.end}]");
            }

            Console.ReadKey();
        }

        public static List<Interval> Merge(List<Interval> intervals, int mergeDistance)
        {
            var result = new List<Interval>();

            for (int i = 0; i < intervals.Count; i++)
            {
                var newInterval = new Interval(intervals[i].start, intervals[i].end);
                //while (i < intervals.Count - 1 && newInterval.end >= intervals[i + 1].start)
                while (i < intervals.Count - 1 && newInterval.end <= mergeDistance) //  intervals[i + 1].start)
                {
                    newInterval.end = Math.Max(newInterval.end, intervals[i + 1].end);
                    i++;
                }

                result.Add(newInterval);
            }

            return result;
        }
    }

 

public class Interval
    {
        public int start { get; set; }
        public int end { get; set; }

        public Interval()
        {

        }

        public Interval(int start, int end)
        {
            this.start = start;
            this.end = end;
        }
    }

标签： c#algorithmmergeintervals

Answer 1

你能试试这个代码吗，工作演示代码在这里

 class Program
    {
        static void Main(string[] args)
        {
            var intervals = new List<Interval>
            {
                new Interval
                {
                    start = 1,
                    end = 20,
                    isAdded = true
                },
                new Interval
                {
                    start = 55,
                    end = 58,
                    isAdded = true
                },
                new Interval
                {
                    start = 60,
                    end = 89,
                    isAdded = true
                },
                new Interval
                {
                    start = 15,
                    end = 31,
                    isAdded = true
                },
                new Interval
                {
                    start = 10,
                    end = 15,
                    isAdded = true
                },
                new Interval
                {
                    start = 1,
                    end = 20,
                    isAdded = false
                }
            };

            var mergedIntervals = Merge(intervals, 7);

            foreach (var item in mergedIntervals)
            {
                Console.WriteLine($"[{item.start}, {item.end}]");
            }

            Console.ReadKey();
        }

        public static List<Interval> Merge(List<Interval> intervals, int mergeDistance)
        {
            var result = new List<IntervalGroup>();
            var group = new IntervalGroup();
            foreach (var item in intervals)
            {
                group = result.Where(c => c.Groups.Any(g =>
                Math.Abs(g.end - item.start) <= mergeDistance ||
                Math.Abs(g.end - item.end) <= mergeDistance)).FirstOrDefault();
                if (group != null && item.isAdded)
                {
                    group.Groups.Add(item);
                }
                else if(item.isAdded)
                {
                    group = new IntervalGroup();
                    group.Groups = new List<Interval>();
                    result.Add(group);
                    group.Groups.Add(item);
                }
                else if(item.isAdded == false)
                {
                    group.Groups.Remove(group.Groups.Where(c => c.start == item.start && c.end == item.end).First());
                }
            }

            var finalResult = result.Select(s => new Interval { start = s.Groups.Min(min => min.start), end = s.Groups.Max(min => min.end) });
            return finalResult.ToList();
        }
    }

    public class Interval
    {
        public int start { get; set; }
        public int end { get; set; }

        public bool isAdded { get; set; }

        public Interval()
        {

        }

        public Interval(int start, int end, bool isAdded)
        {
            this.start = start;
            this.end = end;
            this.isAdded = isAdded;
        }
    }

    public class IntervalGroup
    {
        public List<Interval> Groups { get; set; }
    }