【你有更好的算法嗎？】合并重疊時(shí)間段算法

今天在博問中看到一個(gè)比較常見的問題：求算法(合并重疊時(shí)間段)

在這里先把問題描述一下：

同一天中的一連串不連續(xù)時(shí)間段,合并其中重疊時(shí)間,如:
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
...
時(shí)間復(fù)雜度盡量避免n^2的情況,即集合內(nèi)任一元素與其他元素各比較一次

這樣類似的問題很常見，下面把我的答案帖出來供大家拍磚，也歡迎大家提出更好的算法

代碼：

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()
        {
            //先對數(shù)據(jù)排序
            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)
                {
                    //處理后一條數(shù)據(jù)的結(jié)束時(shí)間比前一條數(shù)據(jù)結(jié)束時(shí)間小的情況
                    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; }
    }

調(diào)用代碼（很簡單啦）：

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

結(jié)果：

歡迎大家提出更高效的算法啦！

非常感謝青龍白虎的意見，經(jīng)檢查程序確實(shí)有問題，主要在第二條數(shù)據(jù)的結(jié)束時(shí)間比第一條數(shù)據(jù)的結(jié)束時(shí)間還小及數(shù)據(jù)未排序的時(shí)候，現(xiàn)已更改

posted @ 2011-03-01 15:19 artwl 閱讀(4640) 評論(1) 收藏舉報(bào)

刷新頁面返回頂部

個(gè)人簡介

var ME = {
	"name": "土豆/Artwl",
	"job": "coding",
	"languages": [
		"JS", "HTML",
                "CSS", "jQuery"
		"MVC",".NET",
		"設(shè)計(jì)模式"
	],
	"hobby": [
		"閱讀", "旅游",
		"音樂", "電影"
	]
}

TOP

【你有更好的算法嗎？】合并重疊時(shí)間段算法

公告

個(gè)人簡介

【你有更好的算法嗎？】合并重疊時(shí)間段算法