欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-05 10:48:05
...

日期交集

早在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个时间段的交集呢?

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

请关注下一篇博客