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

发布时间:2017-3-2 3:55:42 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"c# 合并重叠时间段的算法 ",主要涉及到c# 合并重叠时间段的算法 方面的内容,对于c# 合并重叠时间段的算法 感兴趣的同学可以参考一下。

 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_Chao10     {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             else54             {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                     else16                     {17                         extractList[j].StartPoint = extractList[i].StartPoint;18                     }19                     extractList[i] = null;20                 }21                 else22                 {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_Zhang12     {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                 else87                 {88                     i++;89                 }90             }91             extractListNew = list;92         }93     }94 }
View Code

 更多方案见百度云盘:

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

思路决定程序出路

    ---逻辑与思维


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

 

 


上一篇:dede无子栏目的栏目直接调用顶级栏目(不让调用的解决方法) noself=\'yes\'
下一篇:断今天日期和指定日期相等和两者的时间差为两年的sql

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。