• 排序， start升序，end降序 （贪心思想）
  • 画图
  • 区间有三种情况：覆盖、相交、不相交

    1. 线段区间

    ```cpp // [s1, e1] 、 [s2, e2] // 相交 int start = max(s1, s2); int end = min(e1, e2); if (start <= end) { return true; // 有交集 }

if (e1 >= e2) { // 覆盖 } else if (e1 < s2) { // 不相交 } else { // 相交 }

// 1288.删除被覆盖区间 class Solution { public: static bool cmp(vector& a, vector& b) { if (a[0] != b[0]) { return a[0] < b[0]; } return a[1] > b[1]; }

  1. int removeCoveredIntervals(vector<vector<int>>& intervals) {
  2.     sort(intervals.begin(), intervals.end(), cmp);
  3.     int start = intervals[0][0];
  4.     int end = intervals[0][1];
  5.     int count = -1;
  6.     for (auto &it: intervals) {
  7.         // 覆盖
  8.         if (start <= it[0] && end >= it[1]) {
  9.             count++;
  10.         } else if (end >= it[0]) { // 相交
  11.             end = max(end, it[1]);
  12.         } else {
  13.             start = it[0];
  14.             end = it[1];
  15.         }
  17.     }
  18.     return intervals.size() - count;
  19. }

};

// 56.合并区间 class Solution { public: static bool cmp(vector& a, vector& b) { if (a[0] != b[0]) { return a[0] < b[0]; } return a[1] > b[1]; }

  1. vector<vector<int>> merge(vector<vector<int>>& intervals) {
  2.     sort(intervals.begin(), intervals.end(), cmp);
  4.     vector<vector<int>> ans;
  5.     int start = intervals[0][0];
  6.     int end = intervals[0][1];
  7.     for (int i = 1; i < intervals.size(); i++) {
  8.         // 重叠，或者覆盖
  9.         if (end >= intervals[i][0]) {
  10.             end = max(end, intervals[i][1]);
  11.         } else {
  12.             ans.push_back({start, end});
  13.             start = intervals[i][0];
  14.             end = intervals[i][1];
  15.         }
  16.     }
  17.     ans.push_back({start, end});
  18.     return ans;
  20. }

}; // 986.区间列表的交集 class Solution { public: vector> intervalIntersection(vector>& firstList, vector>& secondList) {

  1.     vector<vector<int>> ans;
  2.     int i = 0;
  3.     int j = 0;
  4.     while (i < firstList.size() && j < secondList.size()) {
  5.         // 求交集，小技巧
  6.         int start = max(firstList[i][0], secondList[j][0]);
  7.         int end = min(firstList[i][1], secondList[j][1]);
  8.         if (start <= end) {
  9.             ans.push_back({start, end});
  10.         }
  11.         // 需要注意指针的移动
  12.         if (firstList[i][1] < secondList[j][1]) {
  13.             i++;
  14.         } else {
  15.             j++;
  16.         }
  17.     }
  18.     return ans;
  19. }

}; ```

2. 坐标区间