题解 | #奶牛喂养时间# 贪心

知识点

区间合并 贪心

思路

经典区间合并问题，按照左端点排序，相等的话按照右端点排序。维护当前加入段的左右端点，只有下一段的左端点在当前段的右端点右边，不能并入同一段，把当前段加入后，重置加入的段。剩下的情况都是可以加入的。

时间复杂度

主要瓶颈在排序上，

AC code（C++）

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals int整型vector<vector<>> 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > mergeTimeIntervals(vector<vector<int> >& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> res;
        int n = intervals.size();
        int st = intervals[0][0], ed = intervals[0][1];
        for (int i = 1; i < n; i ++) {
            if (ed < intervals[i][0]) {
                res.push_back({st, ed});
                st = intervals[i][0], ed = intervals[i][1];
            }
            else {
                st = min(st, intervals[i][0]);
                ed = max(ed, intervals[i][1]);
            }
        }
        res.push_back({st, ed});
        return res;
    }
};