# **Leetcode筆記(Meeting Rooms)**

:::info
:information_source: 題目 : Meeting Rooms, 類型 : interval , 等級 : easy
日期 : 2023/04/17，2023/05/06，2023/07/26
:::

lintcode
https://www.lintcode.com/problem/920/

### 嘗試

不大確定要怎麼sort

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: if a person could attend all meetings
    """
    def can_attend_meetings(self, intervals: List[Interval]) -> bool:
        for i in range(len(intervals) - 1):
            if intervals[i].end > intervals[i + 1].start:
                return False
            return True

2023/05/06

錯誤語法
intervals.sort(key = lambda x : x.start)
沒有處理到是空的情況，導致顯示list index out of range
if not intervals: return True


class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: if a person could attend all meetings
    """
    def can_attend_meetings(self, intervals: List[Interval]) -> bool:
        intervals.sort(key=lambda x: x.start)
        
        if not intervals:
            return True

        pre_end = intervals[0].end

        for i in range(1, len(intervals)):
            if intervals[i].start < pre_end:
                return False
            pre_end = intervals[i].end
        return True

2023/07/26
先sort，如果x的結尾大於x + 1的開頭，則有重疊

1.newInter = sorted(intervals, key=lambda Interval: Interval.start)
2.intervals.sort(key=lambda x: x.start)

class Solution:
    def can_attend_meetings(self, intervals: List[Interval]) -> bool:
        if not intervals:
            return True

        newInter = sorted(intervals, key=lambda Interval: Interval.start)
        lastEnd = newInter[0].end

        for i in newInter[1 : ]:
            if lastEnd > i.start:
                return False
            else:
                lastEnd = i.end
        
        return True

---
### **優化**

这个函数的时间复杂度为$O(n\log n)$，这是因为函数中有一个排序操作，排序后，只需要遍历一遍会议列表，检查相邻的会议是否有时间冲突即可，这一步操作的时间复杂度为 $O(n)$。因此，总的时间复杂度为 $O(n\log n)$。
空间复杂度取决于排序算法的实现方式。如果使用的是原地排序算法，那么空间复杂度为 $O(1)$；如果使用的是非原地排序算法，那么空间复杂度将取决于排序算法的实现方式，通常为 $O(n)$ 或 $O(\log n)$。由于 Python 中的 Timsort 是一种非原地排序算法，因此这个函数的空间复杂度为 $O(n)$。

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: if a person could attend all meetings
    """
    def can_attend_meetings(self, intervals: List[Interval]) -> bool:

        intervals.sort(key=lambda x: x.start)
        
        for i in range(len(intervals) - 1):
            if intervals[i].end > intervals[i + 1].start:
                return False
        return True

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success
使用 lambda 关键字可以创建一个匿名函数，该函数可以接收任意数量的参数，并返回一个表达式的结果

lambda arguments: expression

其中，arguments 是一个或多个参数名，用逗号分隔；expression 是一个表达式，用于计算并返回函数的结果。

lambda x: x.start 

来定义一个匿名函数，该函数接收一个参数 x，并返回 x.start

intervals.sort(key=lambda x: x.start)

key 参数指定了用于排序的键，即按照每个区间的开始时间进行排序，从而得到一个按照开始时间升序排列的区间列表。
:::

**思路**

**講解連結**
sort文檔
https://docs.python.org/zh-tw/3/howto/sorting.html

###### tags: `interval` `easy` `leetcode`