【你有更好的算法吗?】合并重叠时间段算法

简介:

今天在博问中看到一个比较常见的问题: 求算法(合并重叠时间段)

在这里先把问题描述一下:

 

同一天中的一连串不连续时间段,合并其中重叠时间,如:
StartTime EndTime
06:10:58 08:15:28
07:38:56 10:34:45
10:55:00 11:34:00
13:09:34 17:45:23
14:23:12 15:24:14
16:14:25 17:52:15
...
合并后为:
StartTime EndTime
06:10:58 10:34:45
10:55:00 11:34:00
13:09:34 17:52:15
...
时间复杂度尽量避免n^2的情况,即集合内任一元素与其他元素各比较一次

这样类似的问题很常见,下面把我的答案帖出来供大家拍砖,也欢迎大家提出更好的算法

 代码:

public   class  bw22617
    {
        
private  List < Betime >  timeList  =   new  List < Betime > () { 
            
new  Betime{BeginTime = new  DateTime( 2011 , 3 , 1 , 10 , 55 , 0 ),EndTime = new  DateTime( 2011 , 3 , 1 , 11 , 34 , 0 )},
            
new  Betime{BeginTime = new  DateTime( 2011 , 3 , 1 , 13 , 9 , 34 ),EndTime = new  DateTime( 2011 , 3 , 1 , 17 , 45 , 23 )},
            
new  Betime{BeginTime = new  DateTime( 2011 , 3 , 1 , 14 , 23 , 12 ),EndTime = new  DateTime( 2011 , 3 , 1 , 15 , 24 , 14 )},
            
new  Betime{BeginTime = new  DateTime( 2011 , 3 , 1 , 7 , 38 , 56 ),EndTime = new  DateTime( 2011 , 3 , 1 , 10 , 34 , 45 )},
            
new  Betime{BeginTime = new  DateTime( 2011 , 3 , 1 , 6 , 10 , 58 ),EndTime = new  DateTime( 2011 , 3 , 1 , 8 , 15 , 28 )},
            
new  Betime{BeginTime = new  DateTime( 2011 , 3 , 1 , 16 , 14 , 25 ),EndTime = new  DateTime( 2011 , 3 , 1 , 17 , 52 , 15 )}
        };

        
public   void  Union()
        {
            
// 先对数据排序
            timeList  =  timeList.OrderBy(p  =>  p.BeginTime).ToList < Betime > ();
            
for  ( int  i  =   0 ; i  <  timeList.Count - 1 ;i ++  )
            {
                
int  j = i + 1 ;
                
if  (timeList[i].EndTime  >=  timeList[j].BeginTime)
                {
                    
// 处理后一条数据的结束时间比前一条数据结束时间小的情况
                     if  (timeList[i].EndTime  >=  timeList[j].EndTime)
                    {
                        timeList[j] 
=  timeList[i];
                    }
                    
else
                    {
                        timeList[j].BeginTime 
=  timeList[i].BeginTime;
                    }
                    timeList[i] 
=   null ;
                }
                
else
                {
                    i
++ ;
                }
            }

            timeList.ForEach(
                
delegate (Betime p)
                {
                    
if  (p  !=   null )
                    {
                        Console.WriteLine(
" BeginTime:  " + p.BeginTime + " \tEndTime:  " + p.EndTime);
                    }
                }
            );
        }
    }
    
public   class  Betime
    {
        
public  DateTime BeginTime {  get set ; }
        
public  DateTime EndTime {  get set ; }
    }

调用代码(很简单啦):

         static   void  Main( string [] args)
        {
            bw22617 test 
=   new  bw22617();
            test.Union();
            Console.Read();
        }

 结果:


 

 欢迎大家提出更高效的算法啦!

 非常感谢青龙白虎 的意见,经检查程序确实有问题,主要在第二条数据的结束时间比第一条数据的结束时间还小及数据未排序的时候,现已更改

 


本文转自Artwl博客园博客,原文链接:http://www.cnblogs.com/artwl/,如需转载请自行联系原作者

相关文章
|
算法 测试技术 C++
C++算法:合并 K 个升序链表
C++算法:合并 K 个升序链表
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
249 2
|
存储 算法
数据结构和算法学习记录——删除有序数组中的重复项、合并两个有序数组
数据结构和算法学习记录——删除有序数组中的重复项、合并两个有序数组
111 0
数据结构和算法学习记录——删除有序数组中的重复项、合并两个有序数组
|
算法 Java
算法题 合并两个有序数组
算法题 合并两个有序数组
75 1
|
设计模式 算法 Java
【数据结构和算法】交替合并字符串
给你两个字符串word1和word2。请你从word1开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。返回合并后的字符串。
228 1
|
存储 SQL 算法
flink cdc 算法问题之low hign点位有重叠如何解决
Flink CDC(Change Data Capture)是一个基于Apache Flink的实时数据变更捕获库,用于实现数据库的实时同步和变更流的处理;在本汇总中,我们组织了关于Flink CDC产品在实践中用户经常提出的问题及其解答,目的是辅助用户更好地理解和应用这一技术,优化实时数据处理流程。
|
存储 算法 前端开发
前端算法专栏-数组-88.合并两个有序数组
前端算法专栏-数组-88.合并两个有序数组
|
存储 算法 前端开发
前端算法-合并两个有序数组
前端算法-合并两个有序数组
|
算法 测试技术 C#
C++前缀和算法:合并石头的最低成本原理、源码及测试用例(二)
C++前缀和算法:合并石头的最低成本原理、源码及测试用例
|
机器学习/深度学习 算法 测试技术
C++前缀和算法:合并石头的最低成本原理、源码及测试用例(一)
C++前缀和算法:合并石头的最低成本原理、源码及测试用例

热门文章

最新文章