问题原型：

有4间房，分别用1、2、3、4表示，黄色部分是可以入住，白色部分不能入住，客人预订了24到28号的房间，为了入住让客户换房最少，计算出最优算法!

理想结果：

24~25号住2号房，26至27号住4号房，28号住2或3号房，客户只需换房2次即可达到要求。

建表造数据

--********************************************************

--创建房态表

CREATETABLE[dbo].[RoomStatus](

    [id][int]IDENTITY(1,1)NOTNULL,

    [RoomDate][date]NULL,--日期

    [RoomCode][varchar](50)NULL,--房间code

    [Status][bit]NULL,--房间状态，为可入住，为不可入住

CONSTRAINT[PK_RoomStatus]PRIMARYKEYCLUSTERED

(

    [id]ASC

)WITH (PAD_INDEX=OFF,STATISTICS_NORECOMPUTE=OFF,IGNORE_DUP_KEY=OFF,ALLOW_ROW_LOCKS=ON,ALLOW_PAGE_LOCKS=ON)ON[PRIMARY]

)ON[PRIMARY]

GO

--********************************************************

--充填数据

SETANSI_PADDINGOFF

GO

SETIDENTITY_INSERT[dbo].[RoomStatus]ON

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (1,CAST(0xEC380B00 ASDate),N‘001‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (2,CAST(0xED380B00 ASDate),N‘001‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (3,CAST(0xEE380B00 ASDate),N‘001‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (4,CAST(0xEF380B00 ASDate),N‘001‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (5,CAST(0xF0380B00 ASDate),N‘001‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (6,CAST(0xF1380B00 ASDate),N‘001‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (7,CAST(0xEC380B00 ASDate),N‘002‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (8,CAST(0xED380B00 ASDate),N‘002‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (9,CAST(0xEE380B00 ASDate),N‘002‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (10,CAST(0xEF380B00 ASDate),N‘002‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (11,CAST(0xF0380B00 ASDate),N‘002‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (12,CAST(0xF1380B00 ASDate),N‘002‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (13,CAST(0xEC380B00 ASDate),N‘003‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (14,CAST(0xED380B00 ASDate),N‘003‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (15,CAST(0xEE380B00 ASDate),N‘003‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (16,CAST(0xEF380B00 ASDate),N‘003‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (17,CAST(0xF0380B00 ASDate),N‘003‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (18,CAST(0xF1380B00 ASDate),N‘003‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (19,CAST(0xEC380B00 ASDate),N‘004‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (20,CAST(0xED380B00 ASDate),N‘004‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (21,CAST(0xEE380B00 ASDate),N‘004‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (22,CAST(0xEF380B00 ASDate),N‘004‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (23,CAST(0xF0380B00 ASDate),N‘004‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (24,CAST(0xF1380B00 ASDate),N‘004‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (25,CAST(0xEC380B00 ASDate),N‘005‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (26,CAST(0xED380B00 ASDate),N‘005‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (27,CAST(0xEE380B00 ASDate),N‘005‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (28,CAST(0xEF380B00 ASDate),N‘005‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (29,CAST(0xF0380B00 ASDate),N‘005‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (30,CAST(0xF1380B00 ASDate),N‘005‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (31,CAST(0xEC380B00 ASDate),N‘006‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (32,CAST(0xED380B00 ASDate),N‘006‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (33,CAST(0xEE380B00 ASDate),N‘006‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (34,CAST(0xEF380B00 ASDate),N‘006‘, 0)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (35,CAST(0xF0380B00 ASDate),N‘006‘, 1)

INSERT[dbo].[RoomStatus]([id],[RoomDate],[RoomCode],[Status])VALUES (36,CAST(0xF1380B00 ASDate),N‘006‘, 1)

SETIDENTITY_INSERT[dbo].[RoomStatus]OFF

最终数据

id    RoomDate    RoomCode    Status

1    2014-08-24    001    0

2    2014-08-25    001    1

3    2014-08-26    001    0

4    2014-08-27    001    1

5    2014-08-28    001    0

6    2014-08-29    001    1

7    2014-08-24    002    1

8    2014-08-25    002    1

9    2014-08-26    002    0

10    2014-08-27    002    0

11    2014-08-28    002    1

12    2014-08-29    002    1

13    2014-08-24    003    1

14    2014-08-25    003    0

15    2014-08-26    003    1

16    2014-08-27    003    0

17    2014-08-28    003    1

18    2014-08-29    003    1

19    2014-08-24    004    1

20    2014-08-25    004    0

21    2014-08-26    004    1

22    2014-08-27    004    1

23    2014-08-28    004    0

24    2014-08-29    004    1

25    2014-08-24    005    0

26    2014-08-25    005    1

27    2014-08-26    005    1

28    2014-08-27    005    1

29    2014-08-28    005    0

30    2014-08-29    005    1

31    2014-08-24    006    1

32    2014-08-25    006    0

33    2014-08-26    006    0

34    2014-08-27    006    0

35    2014-08-28    006    1

36    2014-08-29    006    1

完整算法：

--*****************************************************************

--创建临时表，用于充填结果数据

CREATETABLE#table(start_dateDATE,end_dateDATE,RoomCodevarchar(50))

--*****************************************************************

--计算开始

DECLARE@startdateDATE=‘2014-08-24‘

DECLARE@enddateDATE=‘2014-09-28‘

DECLARE@PrevDateDATE

WHILE@startdate<=@enddate

BEGIN

    IF@startdate=@PrevDate

        BREAK

    ;WITH    tAS (

        SELECT    RoomDate,

        DATEDIFF(DAY,RoomDate,DATEADD(DAY,ROW_NUMBER()OVER (PARTITIONBYRoomCodeORDERBYRoomDate),GETDATE()))ASdiff,

        RoomCode,ROW_NUMBER()OVER (PARTITIONBYRoomCodeORDERBYRoomDate)num

        FROM        dbo.RoomStatus

        WHERE    Status= 1 --AND RoomCode=‘002‘

    )

    INSERTINTO#table(start_date,end_date,RoomCode)

    SELECTTOP 1 MIN(RoomDate)ASstart_date,

        CASEWHENMAX(RoomDate)>=@enddateTHEN@enddateELSEMAX(RoomDate)ENDASend_date,

        RoomCode    

    FROM    t

    GROUPBYdiff,RoomCode

    HAVINGMIN(RoomDate)=@startdate

    ORDERBYDATEDIFF(DAY,MAX(RoomDate),MIN(RoomDate))ASC

    SET@PrevDate=@startdate

    SELECT@startdate=DATEADD(DAY,1,MAX(end_date))FROM#table

    PRINT@startdate

END

--*****************************************************************

--得到结果

SELECT*FROM#table

droptable#table

最终结果：

start_date    end_date    RoomCode

2014-08-24    2014-08-25    002

2014-08-26    2014-08-27    004

2014-08-28    2014-08-29    003

分析思路，整个思路被我分解为4步，1到3步为解决孤岛问题的常用步骤，第四步实现孤岛接力：

step 1:按照按照roomcode为标尺，根据日期顺序计算行号:

SELECT    RoomDate,RoomCode,ROW_NUMBER()OVER (PARTITIONBYRoomCodeORDERBYRoomDate)num

FROM        dbo.RoomStatus

WHERE    Status= 1

step 2：生成日期和行号的差:

SELECT    RoomDate,

    DATEDIFF(DAY,RoomDate,DATEADD(DAY,ROW_NUMBER()OVER (PARTITIONBYRoomCodeORDERBYRoomDate),GETDATE()))ASdiff,

    RoomCode,ROW_NUMBER()OVER (PARTITIONBYRoomCodeORDERBYRoomDate)num

FROM        dbo.RoomStatus

WHERE    Status= 1

这里解释一下这样做的原因；

因为在孤岛范围内，这两个序列都以相同的时间间隔来保持增长，所以

这时他们的差值保持不变。只要遇到一个新的孤岛，他们之间的差值就

会增加。这样做的目的为何，第三步将为你说明。

step 3:取出第二个查询中生成的相同的diff的值的"最大roomdate"和"最小roomdate"，取"最大roomdate"和"最小roomdate"差值最大的第一条即可（差值最大，代表连续性越高，即最优）

T-Sql处理孤岛接力问题,布布扣,bubuko.com

T-Sql处理孤岛接力问题