435. 無重疊區間
- LeetCode
思路： 本題是一個去除重疊區間的問題， 首先按照區間的 end_point 排序， 從第二個區間開始， 如果第二個區間和第一個區間有交集， 就要移除第二個區間。 因為容易證明之后的區間區間如果和第一個有交集， 必然和第二個有交集， 反之不成立。 如果第一個區間和第二個沒有交集， end_point 更新到第二個區間的右端， 繼續循環。
難點： 兩個區間不相交的時候記得移動右端點
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x: x[1])ep = intervals[0][1]removes = 0for i in range(1,len(intervals)):if intervals[i][0] < ep:removes += 1ep = min(ep, intervals[i][1])else:ep = intervals[i][1]return removes 763.劃分字母區間
- LeetCode
思路：這個問題雖然包了層string 的皮， 但還是區間相交的問題。 首先循環字符串， 對于字符串中的字符記下它存在的區間， 區間的左端點是第一次出現的位置， 右端點是最后一次出現的位置。 例如 "ababcbacadefegdehijhklij" a 的區間就是 [0, 8]. 接下來要做的就是合并區間，先根據開頭位置排序（其實第一步已經排好了），然后從第二個開始循環所有區間，如果和上一個區間有交集， 合并的區間右端點更新到兩個右端的最大值。 如果沒有交易， 上個區間的 end_point - start_point + 1 就是一段分割后的字符串長度。?
難點： 把string 問題翻譯成區間交集問題。
class Solution:def partitionLabels(self, s: str) -> List[int]:interval_dict = defaultdict(lambda: [0, 0])occurences = set()for i, letter in enumerate(s):if letter in occurences:interval_dict[letter][1] = ielse:occurences.add(letter)interval_dict[letter][0] = i interval_dict[letter][1] = i intervals = list(interval_dict.values())# print(intervals)ans = []cur_sp, cur_ep = intervals[0][0], intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] < cur_ep:cur_ep = max(cur_ep, intervals[i][1])else:ans.append(cur_ep - cur_sp + 1)cur_sp, cur_ep = intervals[i][0], intervals[i][1]ans.append(cur_ep - cur_sp + 1)return ans 56. 合并區間?
- LeetCode
思路： 這不是上一個問題一摸一樣嘛。。。?
難點： 無
class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key = lambda x: x[0])cur_sp, cur_ep = intervals[0][0], intervals[0][1]ans = []for i in range(1, len(intervals)):if intervals[i][0] <= cur_ep:cur_ep = max(cur_ep, intervals[i][1])else:ans.append([cur_sp, cur_ep])cur_sp, cur_ep = intervals[i][0], intervals[i][1]ans.append([cur_sp, cur_ep])return ans
