判断多个区间是否相交

原创
2018/11/26 13:13
阅读数 4.4K

写一个算法判断多个区间是否存在交叉 在很久以前或许我会if else解决问题,随着工龄的增加对这种代码也是不屑一顾,思考良久出现一个方案还不错,提供给类似需求的人参观斧正

试想 多个区间在一个横坐标中 As Ad 分表标示A区间的开始结束,依次类推

—As—Ad———Bs——Cs——Bd————Cd———

在程序中要想表达A区间可以用map实现,As作为A区间的key,Ad作为A区间的value,便可实现区间的一个开始结束的对应关系的描述//是否想交

sections := make(map[float64]float64)

for _, v := range files {

        _, exist := sections[v.InsertTime]

         if exist { //如果key已经存在,那么出现依次想交即有两个Ns是重复的,抛出异常

            return errors.New(strconv.Itoa(exception.VideoSectionError) + "," + exception.MessageMap[exception.VideoSectionError])

         }

  sections[v.InsertTime] = v.InsertTime + v.Duration //组建 多区间map数据结构

}

这样就可以描述 多个区间 接下来就是判断是否想交问题咯,也是关键。

我的思想是 循环多个区间map将他们map的所有键值对加入数组,循环数组,判断数组的元素 N,的下一个元素N+1是否是Ns和Nd v

ar pave []float64 //存放区间键值对数组

for k, v := range sections { //想数组中存值

      pave = append(pave, k)

       pave = append(pave, v)

}

sort.Sort(sort.Float64Slice(pave)) //对数组进行排序

for i, startSection := range pave { //循环数组

       endSection, exist := sections[startSection] //在map数据中取 查询元素 是否为key

       if exist { //如果是key

          if endSection != pave[i+1] && startSection != pave[i+1] { //判断这个key的value是否是数组元素 startSection+1这个元素的值,如果不是,做出现咯相交

              return true

           }

       }

}

return false 到此为止,

核心思想就是多个区间在横坐标中形成一个数组,其中一个数组元素的如果为某个区间的开始那么他的下一个元素必定为这个区间的结束

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部