Sparrow 算法篇 由日期取交集到思维模式

日期交集

早在13年左右的时侯，做过一个系统，功能很简单，做一个日程管理功能，这里边涉及到一个小知识点，就是日期取交集。今天跟大家分享的是从这个点展开的，时间段取交集的话题。

业务逻辑

逻辑很简单，就是一两个日期段取交集，可如果按正常思维去实现，其实日期交集的场景我们可以穷举出来，大概有4种情况

    s1--------------e1
        s2-----------------e2

        s1--------------e1
    s2-----------e2
        

    s1-----------------e1
        s2-------e2

         s1-------e1
    s2-----------------------e2

如果按这种逻辑实现我们的表达式可能至少要写4种，逻辑复杂，且可读性差

逆向思维

这是软件开发中非常重要的思维模式，在程序员数学中有重点介绍。 这里提到的程序员数学，是一套书，包括程序学基础数学，概率论和线性代码，同时也是进入机器学习的基础理论，有兴趣的朋友可以买回来读一读。 我们通过个例子，来实践一下逆向思维。 其实如果按交集的逻辑来看，上面穷举出来有4 种情况。 但我们反过来想 没有交集的情况只有两种可能

                s1-------------e1
    s2------e2

    s1------e1
                s2--------------e2

我们设 两个时间段的日期为s1(start)-e1(end) 和s2-e2 通过逆向推导可以推出出列表达式

这里我们假定

s1<e1 & s2<e2

=>

e2<s1||e1<s2

说明满足该条件是不可能产生交集 上述表达式翻译成业务语言即

第一个时间段已经结束，第二个时间段还没未开始

通过对表达式取非即所有存在交集的情况

!(e2<s1||e1<s2)

=>

e2>=s1&&e1>=s2

这个就可以做为时间取交集的最终表达式

这里有一点非常重要，这个时间段我们有条件的

s1<e1 & s2<e2

这是表达式成立的充分条件

问题

这里我们只是把时间交集的表达式推导出来，我们把该命题扩展一下,目前我们只是取两个时间段的交集，如果取n个时间段的交集呢？

      ---------   ---------------
   ---------    ---   ---
      -------------   -------
    ------     -----------
       ---------    ------------

• 这样的时间段有成百上千条该如何处理?
• 如果我们需要根据具有日期交集的时间段分组呢？
• 如果我们的业务不是日期，而是其他数据类型呢？如何抽象出计算模型？非日期型数据也可以进行分组？

请关注下一篇博客