【你有更好的算法吗?】合并重叠时间段算法-阿里云开发者社区

开发者社区> 技术mix呢> 正文

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

简介:
+关注继续查看

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

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

 

同一天中的一连串不连续时间段,合并其中重叠时间,如:
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 { getset; }
        
public DateTime EndTime { getset; }
    }

调用代码(很简单啦):

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

 结果:


 

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

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

 


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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
HashMap中实现原理及hashcode方法
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/jjf09/article/details/62220701
7 0
2021年度友盟+ APP消息推送白皮书:工作日6-8点通勤时间消息送达率每日最高
友盟+基于卓越的数据技术与算法能力,于2021年联合阿里巴巴达摩院,推出国内首款智能推送,在保障高送达率的基础上提升消息内容可读性和点击率。友盟+推出《2021 年度APP消息推送白皮书》,该白皮书从送达通道、用户送达偏好、分行业送达率等多个角度解读,带您了解行业推送现状的同时,有效提升APP的消息推送送达率。
5 0
全网首发:char数组矩阵转bit的算法
全网首发:char数组矩阵转bit的算法
4 0
Nature | 有机合成的数字化
Nature | 有机合成的数字化
4 0
利用人类神经网络进行蛋白质设计
利用人类神经网络进行蛋白质设计
4 0
全网首发:以字型为例,以bit表示的二维数组矩阵,旋转90、-90
全网首发:以字型为例,以bit表示的二维数组矩阵,旋转90、-90
3 0
数据库索引知识,你要了解的本文都有!
数据库索引好比是一本书前面的目录,能加快数据库的查询速度。索引是对数据库表中一个或多个列(例如,User 表的 ‘姓名’ 列)的值进行排序的结构。
1 0
Nat. Genet. | 基于CRISPRi技术检测增强子与启动子相互作用
Nat. Genet. | 基于CRISPRi技术检测增强子与启动子相互作用
3 0
+关注
2969
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载