理论

常见解法：

1. 以开始排序+判断curr start 与新区间的关系
2. 以结尾排序+判断curr end与新区间的关系
3. 拆分start, end(记录变化)+排序+accumulative
4. 用Heap维持最大/小值信息
5. 用hash解
6. 化为1D有序数列+二分法
7. 两个数组分别排序+双指针

Tips:

1. 对于inclusive 闭区间[a, b], 用b + 1来计数， e.g (a, 1), (b + 1, -1)

Problems

1. 以开始排序+判断curr start 与新区间的关系

56. Merge Intervals判断新区间start和res[-1]end的关系
57. Insert Interval分为（1）没有与新区间相交（2）与新区间相交，扩大新区间直至没有与别的区间相交（3）加上剩余
252. Meeting Rooms

731. My Calendar II每次遍历数组，count+= start/end,用SortedList保持有序
850. Rectangle Area II化为（y,open/close, x1, x2)并排序，纵向移动扫描线x，每次移动，统计扫描线x所经过区间的长度s(用merge interval的方法），res+= s*(y_cur-y),由区间是开关判断是添加还是减少（x1, x2)\

2. 以结尾排序+判断curr end与新区间的关系

435. Non-overlapping Intervalsgreedy algo:以结尾排序，总是选取较早结束的区间
452. Minimum Number of Arrows to Burst Balloons以结尾排序，类似于435
986. Interval List Intersections双指针，res中放[max(start), min(end)],比较两个end判断更新哪根指针\

3. 拆分start, end(记录变化)+排序+accumulative

253. Meeting Rooms II化为(start, 1), (end,-1)并排序；也可以用heap来track但前meeting个数
759. Employee Free Time排序后，每当cnt==0，设置start,每当cnt!=0且start!=None时，代表休息时间结束，压入res；也可以用heap来记录排队即将开始的工作，curr记录当前进行的工作的最晚结束时间，当heap中pop出下一个开始的工作 > curr时，则代表工作休息间隙
1109. Corporate Flight Bookingsres[i]中先记录变化，再从左到右accumulate res
1589. Maximum Sum Obtained of Any Permutation 2779. Maximum Beauty of an Array After Applying Operation拆分(start, 1),(end+1, -1), 并排序\

4. 用Heap维持最大/小值信息

218. The Skyline Problem依(start,-h,end), (end,0,0）排序，且需保证start在end前面，+ Max heap; 遍历：先heappop出所有结束的房子，再把（height, end)加入heap中，找到heap当前最大高度，若有变化，则加入res
1235. Maximum Profit in Job Scheduling以开始排序，每次pop出heapq中已经结束的项目，更新目前为止最大currProfit， 将新项目的（end, p+currProfit)加入heap中
1882. Process Tasks Using Servers用两个数组，一个记录free server, 一个记录server in progress
3362. Zero Array Transformation III两个heap, inUse + avaiable\

5. 用hash解

554. Brick Wall统计每个位置的裂缝数，找到最多的位置\

6. 化为1D有序数列+二分法

【难】715. Range Module

用一个数组记录区间，其奇数指数为左，右手为右。用bisect left查找区间左端，bisect_right找右端，若返回index为奇数，说明在该区间内，反之则在区域内外，patch所有需要的left, right， 令range[l:r]=patch`

729. My Calendar I类似715， 用一个数组记录区间， 用二分法找到改放入位置，判断l, r是否都在同一区间外，插入用self.bookings[l:r] = [start, end]\

7. 两个数组分别排序+双指针

1229. Meeting Scheduler两个数组分别排序+双指针，每次找到所指区间的overlap，判断是否大于duration, 移动最先结束的区间的指针\