c# 合并重叠时间段的算法

c# 合并重叠时间段的算法

一.采用非排序：

方案一：

使用递归算法，如不喜欢递归的伙伴们，可以使用whie代替。

1.文件：Extract_Chao.cs（核心）

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace Extract
 8 {
 9     public class Extract_Chao
10     {
11         List<ExtractInfo> extractList = new List<ExtractInfo>();
12         public void Main()
13         {
14             var list = AddExtract();
15             BuidExtract(list, 0);
16 
17             for (int i = 0; i < extractList.Count; i++)
18             {
19                 if (extractList[i] == null) continue;
20                 Console.WriteLine(extractList[i].StartPoint + "-------" + extractList[i].EndPoint);
21             }
22         }
23 
24         private void BuidExtract(List<ExtractInfo> list, int num)
25         {
26             for (int i = 0; i < list.Count; i++)
27             {
28 　　　　　　　　　　if(i==num)continue;
29 
30                 if (list[i] != null &&list[num]!=null)
31                 {
32                     if (list[i].StartPoint > list[num].StartPoint && list[i].StartPoint <= list[num].EndPoint)
33                     {
34                         if (list[i].EndPoint > list[num].EndPoint)
35                         {
36                             var extractTemp = new ExtractInfo() { StartPoint = list[num].StartPoint, EndPoint = list[i].EndPoint };
37                             list[num] = extractTemp;
38 　　　　　　　　　　　　　　　　//如果数组有变化，那么就重新递归回调，（我的死穴）
39 　　　　　　　　　　　　　　　　　num=0;
40 　　　　　　　　　　            BuidExtract(list,num);
41                         }
42                         list[i] = null;
43                     }
44                 }
45             }
46 
47             num++;
48             
49             if (num < list.Count)
50             {
51                 BuidExtract(list, num);
52             }
53             else
54             {
55                 extractList = list;
56             }
57 
58 
59         }
60 
61         private List<ExtractInfo> AddExtract()
62         {
63             var list = new List<ExtractInfo>();
64             list.Add(new ExtractInfo() { StartPoint = 24, EndPoint = 41 });
65             list.Add(new ExtractInfo() { StartPoint = 58, EndPoint = 75 });
66             list.Add(new ExtractInfo() { StartPoint = 62, EndPoint = 80 });
67             list.Add(new ExtractInfo() { StartPoint = 79, EndPoint = 89 });
68 
69             list.Add(new ExtractInfo() { StartPoint = 5, EndPoint = 10 });
70             list.Add(new ExtractInfo() { StartPoint = 20, EndPoint = 30 });
71             list.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 25 });
72            
73 
74             return list;
75         }
76 
77 
78     }
79 }
View Code

2. 文件：ExtractInfo.cs（实体）

  public class ExtractInfo
    {
        public double StartPoint { get; set; }

        public double EndPoint { get; set; }
    }

3.文件：Program.cs（入口）

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Extract
{
    class Program
    {
        static void Main(string[] args)
        {
          
            Extract_Chao chao = new Extract_Chao();
            chao.Main();

            Console.WriteLine("OK");
            Console.Read();
        }
    }
}

4.运行结果：

方案二：

文件：ExtractPoint_Zhang3.cs（核心代码）

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace Extract
  8 {
  9     /// <summary>
 10     /// 不排序，递归算法，当集合有变化，回调
 11     /// </summary>
 12     public class ExtractPoint_Zhang3
 13     {
 14         List<ExtractInfo> extractList = new List<ExtractInfo>();
 15         public void Main()
 16         {
 17             extractList = AddExtract();
 18             Console.WriteLine("运算前数据如下:");
 19             for (int i = 0; i < extractList.Count; i++)
 20             {
 21                 Console.WriteLine(extractList[i].StartPoint + "---" + extractList[i].EndPoint);
 22             }
 23 
 24             BuidExtract();
 25             Console.WriteLine();
 26             Console.WriteLine("运算后数据如下:");
 27             for (int i = 0; i < extractList.Count; i++)
 28             {
 29                 if (extractList[i] == null) continue;
 30                 Console.WriteLine(extractList[i].StartPoint + "---" + extractList[i].EndPoint);
 31             }
 32         }
 33 
 34         private void BuidExtract()
 35         {
 36             for (int i = 0; i < extractList.Count; i++)
 37             {
 38                 if (IsMerge(i))
 39                 {
 40                     BuidExtract();
 41                 }
 42             }
 43         }
 44 
 45         private bool IsMerge(int num)
 46         {
 47             var isContinue = false;
 48 
 49             for (int i = 0; i < extractList.Count; i++)
 50             {
 51                 if (num == i) continue;
 52 
 53                 if (extractList[i].StartPoint > extractList[num].StartPoint && extractList[i].StartPoint <= extractList[num].EndPoint)
 54                 {
 55                     if (extractList[i].EndPoint > extractList[num].EndPoint)
 56                     {
 57                         var extractTemp = new ExtractInfo() { StartPoint = extractList[num].StartPoint, EndPoint = extractList[i].EndPoint };
 58 
 59                         var tempI = extractList[i];
 60                         var tempNum = extractList[num];
 61                         extractList.Remove(tempI);
 62                         extractList.Remove(tempNum);
 63                         extractList.Add(extractTemp);
 64 
 65                     }
 66                     else
 67                     {
 68                         var tempI = extractList[i];
 69                         extractList.Remove(tempI);
 70                     }
 71 
 72                     isContinue = true;
 73                     break;
 74                 }
 75             }
 76             return isContinue;
 77         }
 78 
 79         private List<ExtractInfo> AddExtract()
 80         {
 81             var list = new List<ExtractInfo>();
 82             //list.Add(new ExtractInfo() { StartPoint = 5, EndPoint = 10 });
 83             //list.Add(new ExtractInfo() { StartPoint = 20, EndPoint = 30 });
 84             //list.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 25 });
 85 
 86             //list.Add(new ExtractInfo() { StartPoint = 24, EndPoint = 41 });
 87             //list.Add(new ExtractInfo() { StartPoint = 58, EndPoint = 75 });
 88             //list.Add(new ExtractInfo() { StartPoint = 62, EndPoint = 80 });
 89             //list.Add(new ExtractInfo() { StartPoint = 79, EndPoint = 89 });
 90             //list.Add(new ExtractInfo() { StartPoint = 89, EndPoint = 100 });
 91 
 92 
 93             list.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 17 });
 94             list.Add(new ExtractInfo() { StartPoint = 28, EndPoint = 43 });
 95             list.Add(new ExtractInfo() { StartPoint = 49, EndPoint = 59 });
 96             list.Add(new ExtractInfo() { StartPoint = 69, EndPoint = 79 });
 97             list.Add(new ExtractInfo() { StartPoint = 85, EndPoint = 91 });
 98             list.Add(new ExtractInfo() { StartPoint = 14, EndPoint = 46 });
 99 
100 
101             return list;
102         }
103 
104 
105     }
106 }
View Code

二.采用排序算法：

方案一：

http://www.cnblogs.com/artwl/archive/2011/03/01/1968044.html

地址失效解决方案：

函数：Union（核心代码）

 1   public void Union()
 2         {
 3             //先对数据排序
 4             extractList = extractList.OrderBy(p => p.StartPoint).ToList<ExtractInfo>();
 5             for (int i = 0; i < extractList.Count - 1; i++)
 6             {
 7                 int j = i + 1;
 8                 if (extractList[i].EndPoint >= extractList[j].StartPoint)
 9                 {
10                     //处理后一条数据的结束时间比前一条数据结束时间小的情况
11                     if (extractList[i].EndPoint >= extractList[j].EndPoint)
12                     {
13                         extractList[j] = extractList[i];
14                     }
15                     else
16                     {
17                         extractList[j].StartPoint = extractList[i].StartPoint;
18                     }
19                     extractList[i] = null;
20                 }
21                 else
22                 {
23                     i++;
24                 }
25             }
26         }
View Code

此算法甚好的，只是不满足我的需求：（上一个终点等于下一个起点的时候）【根据自己的需求选择方案】

例如如下两段时间段：

5-10

10-20

我的需求结果是要合并：5-20

方案二：

文件：ExtractPoint_Zhang.cs（核心代码）

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 
 6 namespace Extract
 7 {
 8     /// <summary>
 9     /// 排序算法
10     /// </summary>
11     public class ExtractPoint_Zhang
12     {
13         List<ExtractInfo> extractListNew = new List<ExtractInfo>();
14 
15         public void Main()
16         {
17             var list = AddExtract();
18 
19             ExtractCombination(list);
20 
21 
22             for (var i = 0; i < extractListNew.Count; i++)
23             {
24                 Console.WriteLine(extractListNew[i].StartPoint + "----" + extractListNew[i].EndPoint);
25             }
26         }
27 
28         List<ExtractInfo> AddExtract()
29         {
30             var extractListOld = new List<ExtractInfo>();
31             //extractListOld.Add(new ExtractInfo() { StartPoint = 5, EndPoint = 10 });
32             //extractListOld.Add(new ExtractInfo() { StartPoint = 20, EndPoint = 30 });
33             //extractListOld.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 25 });
34 
35             //extractListOld.Add(new ExtractInfo() { StartPoint = 24, EndPoint = 41 });
36             //extractListOld.Add(new ExtractInfo() { StartPoint = 58, EndPoint = 75 });
37             //extractListOld.Add(new ExtractInfo() { StartPoint = 62, EndPoint = 80 });
38             //extractListOld.Add(new ExtractInfo() { StartPoint = 79, EndPoint = 89 });
39             //extractListOld.Add(new ExtractInfo() { StartPoint = 89, EndPoint = 100 });
40 
41 
42             extractListOld.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 17 });
43             extractListOld.Add(new ExtractInfo() { StartPoint = 28, EndPoint = 43 });
44             extractListOld.Add(new ExtractInfo() { StartPoint = 49, EndPoint = 59 });
45             extractListOld.Add(new ExtractInfo() { StartPoint = 69, EndPoint = 79 });
46             extractListOld.Add(new ExtractInfo() { StartPoint = 85, EndPoint = 91 });
47             extractListOld.Add(new ExtractInfo() { StartPoint = 14, EndPoint = 46 });
48 
49             return extractListOld;
50         }
51 
52         void ExtractCombination(List<ExtractInfo> list)
53         {
54             var listNew = new List<ExtractInfo>();
55             list = list.OrderBy(x => x.StartPoint).ToList<ExtractInfo>();
56 
57             for (int i = 0; i < list.Count; )
58             {
59                 var num = i + 1;
60 
61                 if (num >= list.Count) break;
62 
63                 if (list[num].StartPoint <= list[i].EndPoint)
64                 {
65                     if (list[num].EndPoint > list[i].EndPoint)
66                     {
67                         var extractTemp = new ExtractInfo();
68                         extractTemp.StartPoint = list[i].StartPoint;
69                         extractTemp.EndPoint = list[num].EndPoint;
70 
71 
72                         var tempI = list[i];
73                         var tempNum = list[num];
74                         list.Remove(tempI);
75                         list.Remove(tempNum);
76                         list.Add(extractTemp);
77                     }
78                     else 
79                     {
80                         var tempI = list[i];
81                         list.Remove(tempI);
82                     }
83                     list = list.OrderBy(x => x.StartPoint).ToList<ExtractInfo>();
84                     i = 0;
85                 }
86                 else
87                 {
88                     i++;
89                 }
90             }
91             extractListNew = list;
92         }
93     }
94 }
View Code

 更多方案见百度云盘：

http://pan.baidu.com/s/1nvjmNtn

思路决定程序出路

　　　　---逻辑与思维


欢迎大家分享更好的算法，独乐不如众乐！　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

 

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zlp520/p/6213581.html