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

一.采用非排序：

方案一：

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

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

 using System;

 using System.Collections.Generic;

 using System.Linq;

 using System.Text;

 using System.Threading.Tasks;

 namespace Extract

 {

     public class Extract_Chao

     {

         List<ExtractInfo> extractList = new List<ExtractInfo>();

         public void Main()

         {

             var list = AddExtract();

             BuidExtract(list, );

             for (int i = ; i < extractList.Count; i++)

             {

                 if (extractList[i] == null) continue;

                 Console.WriteLine(extractList[i].StartPoint + "-------" + extractList[i].EndPoint);

             }

         }

         private void BuidExtract(List<ExtractInfo> list, int num)

         {

             for (int i = ; i < list.Count; i++)

             {

 　　　　　　　　　　if(i==num)continue;

                 if (list[i] != null &&list[num]!=null)

                 {

                     if (list[i].StartPoint > list[num].StartPoint && list[i].StartPoint <= list[num].EndPoint)

                     {

                         if (list[i].EndPoint > list[num].EndPoint)

                         {

                             var extractTemp = new ExtractInfo() { StartPoint = list[num].StartPoint, EndPoint = list[i].EndPoint };

                             list[num] = extractTemp;

 　　　　　　　　　　　　　　　　//如果数组有变化，那么就重新递归回调，（我的死穴）

 　　　　　　　　　　　　　　　　　num=;

 　　　　　　　　　　            BuidExtract(list,num);

                         }

                         list[i] = null;

                     }

                 }

             }

             num++;

             if (num < list.Count)

             {

                 BuidExtract(list, num);

             }

             else

             {

                 extractList = list;

             }

         }

         private List<ExtractInfo> AddExtract()

         {

             var list = new List<ExtractInfo>();

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             return list;

         }

     }

 }

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（核心代码）

 using System;

 using System.Collections.Generic;

 using System.Linq;

 using System.Text;

 using System.Threading.Tasks;

 namespace Extract

 {

     /// <summary>

     /// 不排序，递归算法，当集合有变化，回调

     /// </summary>

     public class ExtractPoint_Zhang3

     {

         List<ExtractInfo> extractList = new List<ExtractInfo>();

         public void Main()

         {

             extractList = AddExtract();

             Console.WriteLine("运算前数据如下:");

             for (int i = ; i < extractList.Count; i++)

             {

                 Console.WriteLine(extractList[i].StartPoint + "---" + extractList[i].EndPoint);

             }

             BuidExtract();

             Console.WriteLine();

             Console.WriteLine("运算后数据如下:");

             for (int i = ; i < extractList.Count; i++)

             {

                 if (extractList[i] == null) continue;

                 Console.WriteLine(extractList[i].StartPoint + "---" + extractList[i].EndPoint);

             }

         }

         private void BuidExtract()

         {

             for (int i = ; i < extractList.Count; i++)

             {

                 if (IsMerge(i))

                 {

                     BuidExtract();

                 }

             }

         }

         private bool IsMerge(int num)

         {

             var isContinue = false;

             for (int i = ; i < extractList.Count; i++)

             {

                 if (num == i) continue;

                 if (extractList[i].StartPoint > extractList[num].StartPoint && extractList[i].StartPoint <= extractList[num].EndPoint)

                 {

                     if (extractList[i].EndPoint > extractList[num].EndPoint)

                     {

                         var extractTemp = new ExtractInfo() { StartPoint = extractList[num].StartPoint, EndPoint = extractList[i].EndPoint };

                         var tempI = extractList[i];

                         var tempNum = extractList[num];

                         extractList.Remove(tempI);

                         extractList.Remove(tempNum);

                         extractList.Add(extractTemp);

                     }

                     else

                     {

                         var tempI = extractList[i];

                         extractList.Remove(tempI);

                     }

                     isContinue = true;

                     break;

                 }

             }

             return isContinue;

         }

         private List<ExtractInfo> AddExtract()

         {

             var list = new List<ExtractInfo>();

             //list.Add(new ExtractInfo() { StartPoint = 5, EndPoint = 10 });

             //list.Add(new ExtractInfo() { StartPoint = 20, EndPoint = 30 });

             //list.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 25 });

             //list.Add(new ExtractInfo() { StartPoint = 24, EndPoint = 41 });

             //list.Add(new ExtractInfo() { StartPoint = 58, EndPoint = 75 });

             //list.Add(new ExtractInfo() { StartPoint = 62, EndPoint = 80 });

             //list.Add(new ExtractInfo() { StartPoint = 79, EndPoint = 89 });

             //list.Add(new ExtractInfo() { StartPoint = 89, EndPoint = 100 });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             list.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             return list;

         }

     }

 }

二.采用排序算法：

方案一：

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

地址失效解决方案：

函数：Union（核心代码）

   public void Union()

         {

             //先对数据排序

             extractList = extractList.OrderBy(p => p.StartPoint).ToList<ExtractInfo>();

             for (int i = ; i < extractList.Count - ; i++)

             {

                 int j = i + ;

                 if (extractList[i].EndPoint >= extractList[j].StartPoint)

                 {

                     //处理后一条数据的结束时间比前一条数据结束时间小的情况

                     if (extractList[i].EndPoint >= extractList[j].EndPoint)

                     {

                         extractList[j] = extractList[i];

                     }

                     else

                     {

                         extractList[j].StartPoint = extractList[i].StartPoint;

                     }

                     extractList[i] = null;

                 }

                 else

                 {

                     i++;

                 }

             }

         }

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

例如如下两段时间段：

5-10

10-20

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

方案二：

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

 using System;

 using System.Collections.Generic;

 using System.Linq;

 using System.Text;

 namespace Extract

 {

     /// <summary>

     /// 排序算法

     /// </summary>

     public class ExtractPoint_Zhang

     {

         List<ExtractInfo> extractListNew = new List<ExtractInfo>();

         public void Main()

         {

             var list = AddExtract();

             ExtractCombination(list);

             for (var i = ; i < extractListNew.Count; i++)

             {

                 Console.WriteLine(extractListNew[i].StartPoint + "----" + extractListNew[i].EndPoint);

             }

         }

         List<ExtractInfo> AddExtract()

         {

             var extractListOld = new List<ExtractInfo>();

             //extractListOld.Add(new ExtractInfo() { StartPoint = 5, EndPoint = 10 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 20, EndPoint = 30 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 6, EndPoint = 25 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 24, EndPoint = 41 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 58, EndPoint = 75 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 62, EndPoint = 80 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 79, EndPoint = 89 });

             //extractListOld.Add(new ExtractInfo() { StartPoint = 89, EndPoint = 100 });

             extractListOld.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             extractListOld.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             extractListOld.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             extractListOld.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             extractListOld.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             extractListOld.Add(new ExtractInfo() { StartPoint = , EndPoint =  });

             return extractListOld;

         }

         void ExtractCombination(List<ExtractInfo> list)

         {

             var listNew = new List<ExtractInfo>();

             list = list.OrderBy(x => x.StartPoint).ToList<ExtractInfo>();

             for (int i = ; i < list.Count; )

             {

                 var num = i + ;

                 if (num >= list.Count) break;

                 if (list[num].StartPoint <= list[i].EndPoint)

                 {

                     if (list[num].EndPoint > list[i].EndPoint)

                     {

                         var extractTemp = new ExtractInfo();

                         extractTemp.StartPoint = list[i].StartPoint;

                         extractTemp.EndPoint = list[num].EndPoint;

                         var tempI = list[i];

                         var tempNum = list[num];

                         list.Remove(tempI);

                         list.Remove(tempNum);

                         list.Add(extractTemp);

                     }

                     else

                     {

                         var tempI = list[i];

                         list.Remove(tempI);

                     }

                     list = list.OrderBy(x => x.StartPoint).ToList<ExtractInfo>();

                     i = ;

                 }

                 else

                 {

                     i++;

                 }

             }

             extractListNew = list;

         }

     }

 }

更多方案见百度云盘：

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

思路决定程序出路

　　　　---逻辑与思维

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

最新文章

  1. java中的成员变量和局部变量区别
  2. MySql技巧个人笔记
  3. Visual Studio版本号对应表
  4. [POJ] 3277 .City Horizon（离散+线段树）
  5. #Leet Code# Evaluate Reverse Polish Notation
  6. android binder机制之——（创建binder服务）
  7. html学习笔记二
  8. 2016-2017 CT S03E02: Codeforces Trainings Season 3 Episode 2
  9. 运行出错之未能加载文件或程序集“Microsoft.ReportViewer.Common, Version=12.0.0.0, Culture=neutral, PublicKeyToken=89845dcd8080cc91”或它的某一个依赖项。系统找不到指定的文件。文件名:“Microsoft.ReportViewer.Common, Version=11.0.0.0,
  10. 从聚合数据请求菜谱大全接口数据，解析显示到ListView
  11. iis配置完成，出现HTTP 错误 403.14 - Forbidden
  12. FORM开发两种方式实现动态LIST
  13. Android进阶：一、日志打印和保存策略
  14. [Swift]LeetCode726. 原子的数量 | Number of Atoms
  15. May 31. 2018 Week 22nd Thursday
  16. centos7下kubernetes（9。kubernetes中用label控制pod得位置）
  17. MySQL修改root密码教程
  18. Mina2 udp--zhengli
  19. bzoj千题计划199：bzoj1055: [HAOI2008]玩具取名
  20. Android Support Palette使用详解

热门文章

  1. IIS 访问不了，IIS有问题，IIS右击浏览没反应
  2. MongoDB的数据类型（四）
  3. Java中spring读取配置文件的几种方法
  4. git format-patch 用法【转】
  5. EXPAT(XML解析库)
  6. 剑指offer面试题3二维数组中的查找
  7. python中的日志模块logging
  8. hadoop 学习（一）ubuntu14.04 hadoop 安装
  9. 2018.09.19 atcoder AtCoDeer and Election Report（贪心）
  10. vi 基本使用命令