求个算法问题，各数学帝快来

Question

有N组数值范围例如 1-99
101-155
88-200
4-300
301-400
....怎样判断这组数字区间范围有重复就比如上面的这一组
找过 1-99 与 88-200 这2组数值区间是重复的

Answer 1

首先找出一个上限值最大的组合，假设上限值最大是N
然后在1 到 N之间循环
 for(1...N)
  for(组合[0]...组合[length])
   如果当前值i在某一区间内就把当前区间记录到一个数组里

Answer 2

不知道是不是你要的结果，最好是能把重复的过滤掉，哈哈，这个就由楼主来完成吧 class Program
    {
        static void Main(string[] args)
        {
            ArrayList Intervals = new ArrayList();
            List<ArrayList> result = new List<ArrayList>();
            Intervals.Add(new Interval(2,59));
            Intervals.Add(new Interval(1, 47));
            Intervals.Add(new Interval(67, 98));
            Intervals.Add(new Interval(3, 50));
            Intervals.Add(new Interval(19, 29));
            Intervals.Add(new Interval(100, 509));
            Intervals.Add(new Interval(14, 74));
            Intervals.Add(new Interval(10, 50));
            Intervals.Add(new Interval(23, 25));
            Intervals.Add(new Interval(18, 28));
            Intervals.Add(new Interval(2, 20));
            Intervals.Sort();
            int maxNumber = ((Interval)Intervals[0]).Max;
            for (int i = 1; i < maxNumber; i++)
            {
                ArrayList temp =new ArrayList();
                foreach (Interval v in Intervals)
                {
                    if (v.IsInterval(i))
                    {
                        temp.Add(v);
                    }
                }
                if (temp.Count > 1)
                {
                    result.Add(temp);
                }
            }
            int s = 0;
        }
    }
    public class Interval:IComparable,IEnumerable
    {
        private int _min;        public int Min
        {
            get { return _min; }
            set { _min = value; }
        }
        private int _max;        public int Max
        {
            get { return _max; }
            set { _max = value; }
        }
        private int _maxValue;        public int MaxValue
        {
            get { return _maxValue; }
            set { _maxValue = value; }
        }
        public Interval(int min ,int max)
        {
            if (min > max)
            {
                _min = max;
                _max = min;
            }
            else
            {
                _min = min;
                _max = max;
            }
        }
        public bool IsInterval(int valu)
        {
            if (valu > _min && valu < _max)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
  
        public int CompareTo(object obj)
        {
            Interval temp = (Interval)obj;
            return temp._max - this._max;
        }
        public IEnumerator GetEnumerator()
        {
            return new ArrayList().GetEnumerator();
        }
    }

Answer 3

Point[] points = {
                     new Point(1,99),
                     new Point(101,155),
                     new Point(80,200),
                     new Point(4, 300),
                     new Point(301, 400)
                 };
Array.Sort(points, (p1, p2) => p1.X - p2.X);
for (int i = 1; i < points.Length; i++)
{
    if (points[i].X < points[i - 1].Y)
    {
        MessageBox.Show("Overlapped: " + points[i-1] + " ~ " + points[i]);
    }
}

Answer 4

不太明白搂主的意思,如果只是想知道n各区间数有没有重复,只要找的这些区间数的最小值集合和最大值集合,然后比较最小值集合的最大值和最大值集合的最小值就OK了,例: 
1-99
101-155
88-200
4-300
301-400
最小值的集合是(1,101,88,4,301)         最大值是301,
最大值的集合是(99,155,200,300,400)     最小值是99.
99<301,所以肯定有重复的.

Answer 5

这里的比较有缺陷，如果第一组是new poing(1,156) 它的结果是与第二组new point(101,155)没有重复（无 overlap） .应该是这样： Point[] points = {
                     new Point(1,156),
                     new Point(101,155),
                     new Point(80,200),
                     new Point(4, 300),
                     new Point(301, 400)
                 };
            Array.Sort(points, (p1, p2) => p1.X - p2.X);
            for (int i = 1; i < points.Length; i++)
            {
                int X2=points[i].X,X1= points[i-1].X,Y1=points[i-1].Y,Y2=points[i].Y;
                
                if (!((X1<X2 && Y1<X2) || (X2<X1 && Y2<Y1)))
                {
                    Response.Write("Overlapped: " + points[i - 1] + " ~ " + points[i]);
                }
            }

Answer 6

[Quote=引用 16 楼 fengppandbt 的回复:]
12楼的方法是可以的
排过序之后x2一定大于x1.
只要x2小于y1 就可以.

Answer 7

只求重复的话，按照起点排个序，然后遍历一遍，看有没有起点大于前面的终点的即可n*log(n)的，求全部重复区间的话，可以用线段树，不过最坏情况下是n^2的。

Answer 8

Very easy.
用没个区间的端点去跟其他区间的端点比较即可知道。是否有重叠

Answer 9

改了一下上面几位的程序
using System;namespace CsdnTest
{
    class Program
    {
        struct Point
        {
            public int Start;
            public int End;
            public Point(int s, int e) { Start = s; End = e; }
        }        static void Main(string[] args)
        {
            Point[] points = { new Point(1, 80), new Point(60, 70), new Point(70, 80), new Point(80, 300), new Point(301, 400) };
            Array.Sort(points, (p1, p2) => p1.Start.CompareTo(p2.Start));            int max = points[0].End, index = 0;            for (int i = 1; i < points.Length; i++)
            {
                if (points[i].Start < max)
                    Console.WriteLine("{0}->{1} {2}->{3}", points[index].Start, points[index].End, points[i].Start, points[i].End);                if (points[i].End > max)
                {
                    max = points[i].End;
                    index = i;
                }
            }            Console.ReadKey();
        }
    }
}