一个递归问题的简单解法

发表于 分类于 阅读次数： 阅读次数： 本文字数： 528 阅读时长 ≈ 2 分钟

问题：

问题来源:hackerrank-SQL-Projects

问题翻译过来大致是：有一个表__projects__ ,表面有3个字段 task_id , start_date , end_date 。end_date__永远比__start_date__大一天。如果__end_date__是连续的，即__end_date == start_date ,那么连续的task是同一个project的任务。求每个project的起始时间是多少？

分析问题：

思路1 ： 递归方法

最简单的思路，找到第一个任务的结束时间，根据这个结束时间再去查找下一个开始时间，从而得到下一个的结束时间，重复前面的步骤；如果查找不到开始时间，结束。

但是这里面有一个问题，sql对于递归支持很不友好，写起来很复杂。放弃。

思路2：求所有的开始和结束时间，进行配对。

这个思路是建立在每个task的时间不重合的基础上，幸运的是完全符合本题目的要求。

思路如下：如果一个任务有开始，那么必定有结束；那首尾相接的task,如同链表一样，必定有一个开始和结束。开始时间数和结束时间数相同，且一一匹配。那么求出所有的开始时间和结束时间，按照先后顺序匹配，即得出每个project的时间长度。

解法：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

SELECT
  start_date,
  end_date
FROM (
       SELECT
         @rownum := @rownum + 1 AS rownum,
         Start_Date
       FROM Projects p
         JOIN (SELECT @rownum := 0) b
       WHERE Start_Date NOT IN (SELECT End_Date
                                FROM Projects)) t1
  JOIN (
         SELECT
           @rownum2 := @rownum2 + 1 AS rownum,
           End_Date
         FROM Projects
           JOIN (SELECT @rownum2 := 0) b
         WHERE End_Date NOT IN (SELECT Start_Date
                                FROM Projects)) t2 ON t1.rownum = t2.rownum
ORDER BY DATEDIFF(end_date, start_date), start_date

解释

代码的关键在于，构建了rownum来进行排序，用时间顺序一致的开始和结束时间作为同一对时间来对待。
关键在于求rownum这一部分，其实还应该再加上一个排序，保证时间的先后次序一致。

总结：

这个问题的思考过程中，解决起来的关键点是如何找出数据的规律，代码的复杂度没有想象的那么高，转个弯就好了。