1. class Time {
  2.     public:
  3.         int start;
  4.         int end;
  5.         Time(int s, int e) :start(s), end(e) {}
  6. };//定义时间区间

按end时间排序

最多不重叠区间数

    bool cmp(const Time& t1, const Time& t2) {
        return t1.end < t2.end;
    }
    int countNoOverlap(const vector<int>& vstart, const vector<int>& vend) {
        if (vstart.size() != vend.size() || vstart.empty()) return -1;
        vector<Time> vtime;
        for (int i = 0; i < vstart.size(); ++i)
            vtime.push_back(Time(vstart[i], vend[i]));
        sort(vtime.begin(), vtime.end(),cmp);
        int amount = 0, prevEnd = 0;
        for (int i = 0; i < vtime.size(); ++i) {
            if (prevEnd < vtime[i].start) {
                amount++;
                prevEnd = vtime[i].end;
            }
        }
        return amount;
    }

最长不重叠区间和

现在有n个工作要完成，每项工作分别在 时间开始，在 时间结束。对于每项工作，你都可以选择参与与否。如果选择了参与，那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（闭区间）。求你参与的所有工作最大需要耗费多少时间，另一种说法是：想投入最多时间到工作中，求这个最长时间。 这里动态规划就能很好地求解。

    int noOverlap(const vector<Time>& vtime, int pos, const Time& t) {
        for (int i = pos; i >=0; --i)
            if (vtime[i].end < t.start)
                return i;
        return -1;
    }
    int longestNoOverlap(const vector<int>& vstart, const vector<int>& vend) {
        if (vstart.size() != vend.size() || vstart.empty()) return -1;
        vector<Time> vtime;
        for (int i = 0; i < vstart.size(); ++i)
            vtime.push_back(Time(vstart[i], vend[i]));
        sort(vtime.begin(), vtime.end(), cmp);
        //DP
        int* dp = new int[vtime.size()];
        dp[0] = vtime[0].end - vtime[0].start;
        int longest = dp[0];
        for (int i = 1; i < vtime.size(); ++i) {
            if (int pos = noOverlap(vtime, i, vtime[i]) >= 0)
                longest = dp[pos] + vtime[i].end - vtime[i].start;
            else
                longest = vtime[i].end - vtime[i].start;
            dp[i] = max(dp[i - 1], longest);
        }
        delete[]dp;
        return dp[vtime.size()-1];
    }

带权区间调度(选取价值最大的区间集)

    typedef struct Node {
        int start;
        int end;
        int value;
        Node(int s, int e, int v) :start(s), end(e), value(v) {}
        long long getValue() {
            return value*(end - start);
        }
    } node;
    bool cmpNd(const Node& n1, const Node& n2) {
        return n1.end < n2.end;
    }
    int findNoOverlap(const vector<Node>& wTime, int pos, const Node& node) {
        for (int i = pos; i >= 0; --i)
            if (wTime[i].end < node.start)
                return i;
        return -1;
    }
    int bestValueNoOverlap(const vector<int>& vstart, const vector<int>& vend, const vector<int>& weight) {
        //防御式编程，检查入参的合法性
        //...
        vector<node> wTime;
        for (int i = 0; i < vstart.size(); ++i)
            wTime.push_back(Node(vstart[i], vend[i], weight[i]));
        sort(wTime.begin(), wTime.end(), cmpNd);
        //DP
        long long* dp = new long long[vstart.size()];
        dp[0] = wTime[0].getValue();
        long long best = 0;
        for (int i = 1; i < wTime.size(); ++i) {
            int pos = findNoOverlap(wTime, i, wTime[i]);
            if (pos >= 0)
                best = dp[pos] + wTime[i].getValue();
            else
                best = wTime[i].getValue();
            dp[i] = max(best, dp[i - 1]);
        }
        delete[]dp;
        return dp[wTime.size() - 1];
    }

按start时间排序

覆盖指定区域所需的最少区间数

bool cmp2(const Time& t1, const Time& t2) {
        return t1.start < t2.start;
    }
    int leastRangeToOverlap(vector<Time>& vtime, const int left, const int right,vector<Time>& range) {
        if (vtime.empty() || left >= right) return -1;
        sort(vtime.begin(), vtime.end(), cmp2);
        int n = vtime.size();
        int i = 0;
        int tleft = left;
        int max_right = 0;
        int pos;
        int amount = 0;
        while (i<n)
        {
            while (vtime[i].start <= tleft) {
                if (vtime[i].end > max_right) {
                    max_right = vtime[i].end;
                    pos = i;
                }
                ++i;
            }
            if (max_right > tleft) {
                range.push_back(vtime[pos]);
                amount++;
                tleft = max_right;
                if (tleft >= right)
                    return amount;
                ++i;
            }
            else
                return -1;
        }
        return amount;
    }

区间的最长重叠部分

//先start排序，从左往右扫描，从相邻的区间找出最大的重叠部分

会议房间最佳安排(所用的房间最少)

    typedef struct  Meet {
        int num;
        int time;//开始或结束时间
        int sore;//开始为1,结束为0
        int room = -1;
        Meet(int n, int t, int f) :num(n), time(t), sore(f) {}
    };
    bool cmp3(const Meet& m1, const Meet& m2) {
        if (m1.time == m2.time) return m1.sore < m2.sore;
        return m1.time < m2.time;
    }
    class MeetSchedule {
    public:
        int meetingRoomSchedule(const vector<int>& vstart, const vector<int>& vend, vector<vector<int>>& vret) {
            //防御式编程
            vector<Meet> vtime;
            for (int i = 0; i < vstart.size(); ++i) {
                vtime.push_back(Meet(i, vstart[i], 1));
                vtime.push_back(Meet(i, vend[i], 0));
            }
            sort(vtime.begin(), vtime.end(), cmp3);
            stack<int> stkroom; //准备教室
            for (int i = vstart.size(); i >= 1; --i)
                stkroom.push(i);
            int maxNum = 0;
            for (int i = 0; i < vtime.size() - 1; ++i) {
                if (vtime[i].sore) {
                    maxNum = max(maxNum, stkroom.top());
                    vtime[i].room = stkroom.top();
                    stkroom.pop();
                    setEndRoom(vtime, i, vtime[i]);
                    vret.push_back(vector<int>{vtime[i].num, vtime[i].room});
                }
                else
                    stkroom.push(vtime[i].room);
            }
            return maxNum;
        }
    private:
        void setEndRoom(vector<Meet>& vtime, int pos, Meet& node) {
            for (int i = pos + 1; i < vtime.size(); ++i)
                if (vtime[i].num == node.num)
                    vtime[i].room = node.room;
        }
    };

leetcode 三题

435无重叠区间(低频)

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/non-overlapping-intervals 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        //先排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        //记录区间尾部的位置
        int end = intervals[0][1];
        //需要移除的数量
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                //如果重叠了，必须要移除一个，所以count要加1，
                //两个区间有重复，必须要移除一个，那么要移除哪个呢，为了防止在下一个区间和现有区间有重叠，我们应该让现有区间越短越好，所以应该移除尾部比较大的，保留尾部比较小的。
                end = Math.min(end, intervals[i][1]);
                count++;
            } else {
                //如果没有重叠，就不需要移除，只需要更新尾部的位置即可
                end = intervals[i][1];
            }
        }
        return count;
    }

986区间列表的交集(低频)

给定两个由一些 闭区间 组成的列表，每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。
（形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/interval-list-intersections 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目说，给定的两个区间列表都是排好序的
用两个指针，分别扫描 A、B 数组，根据子区间的左右端，求出一个交集区间
指针移动，直至指针越界，得到由交集区间组成的数组。

const intervalIntersection = (A, B) => {
  const res = [];
  let i = 0;
  let j = 0;
  while (i < A.length && j < B.length) {
    const start = Math.max(A[i][0], B[j][0]); // 交集区间的左端，取它们的较大者
    const end = Math.min(A[i][1], B[j][1]); // 交集区间的右端，取它们的较小者
    if (start <= end) {       // 形成了交集区间
      res.push([start, end]);
    }
    if (A[i][1] < B[j][1]) {  // 谁先结束，谁的指针就步进，考察下一个子区间
      i++;
    } else {
      j++;
    }
  }
  return res;
};

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/interval-list-intersections/solution/jiu-pa-ni-bu-dong-shuang-zhi-zhen-by-hyj8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

56合并区间(中频）

给出一个区间的集合，请合并所有重叠的区间。

//很容易，贪心做法就行。
sort(arr.begin(),arr.end(),[]->{a.start<b.start});
curL=arr[0].start;curR=arr[0].end;
for(int i=1;i<arr.size();++i){
    if(arr[i].start<=curR){
        curR=max(arr[i].end,curR);
    }else{
        ret.add(pair<int,int>(curL,curR));
        curL=arr[i].start;
        curR=arr[i].end;
    }
}
return ret;