meeting or intervals

一道经典题目 但是实战面试遇到了个test case 困惑了我很久

给 list of meetings 然后 再给 new meeting 问是否可以安排 （就是没有overlap）
我开始给的算法：
clase solution
   def isvalide（self，meetings，new）
        meetings append new
       meeting sort
      for i in range( len(meetings)-)
           if meetings[i][1] > meetings[i+1][0]:
              return False
    return True
我这个写法 有个test case 不过，当时我就把排序好的metting打印出来 看了下 肉眼确实看到有overlap 我返回的是 false ，然而答案是 True
但是我问过面试官 meetings 本身是不是有overlap ，他说没有 （我不太确定他说的对不对）
当时时间比较紧 我就没debug 换了写法 用扫线写的 这个case 返回就是True了
扫线法 就是用 dic ，dic[start] += 1, dic[end] -= 1
然后所有key 排序
扫key 累加对应的value 如果超过1就是有overlap， 这个解法返回的就是true

事后，我想返回看看第一问具体什么原因 但是题目被覆盖了 test case 也没了，只有我当时的print out 的 list （既有old meeting 又有新的meeting ）确实是有overlap 的
‍‌‍‍‌‌‍‍‍‌‍‍‌‍‌‌‍‍‌‌我很不解为什么我最初的解法是不过的，（我先前问过面试官 old meeting 是否有overlap 他说没有 但是我不确定他听清楚了么）
谁能说说 为什么有overlap 的时候，扫线法可以返回true 然而我上面的算法不行

还是有什么非常特殊的case 比如首位想接的case 我自己是想了很久 找不到例外

求教高人解释解释

DesongBian 发表于 2022-04-22 09:27:17
应该是实现了

python 里

那区别就是在overlap的定义上了，线扫法支持会议结束可以紧跟会议开始，但楼主的merge interval写法的for loop中的if 写的是> 而不是>= ，所以不支持。

比如test case： [[1,4],[4,8]]，线扫法对于4这个位置，认为是不overlap的，而楼主解法一的实现是判断成overlap的。

补充内容 (2022-04-23 00:46 +08:00):
大意了，回复完再看代码，好像也并不是这个原因

进入for循环之前的meetings sort 是确定实现了 sort by meeting start 么？这行看起来像pseudocode

Java 写的话，是要实现一个comparator的

xiaxiaya 发表于 2022-4-22 01:28
进入for循环之前的meetings sort 是确定实现了 sort by meeting start 么？这行看起来像pseudocode

Java  ...

应该是实现了

python 里

meetings.sort() 就是直接按照第一位排序了