前言
今日文案：
其实，余生并不长，做喜欢的事情，在一个正当好的人，东有飘雪，夏有凉风，以美好的心态对待每一天，尽量把遗憾降到最低，如此才是不辜负自己。
一、无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠
贪心思路：
我们只需要找出单独的区间有多少个，然后总数减去单独区间就是要去掉的区间。
右边界排序，每次取非交叉区间的时候，都是可右边界最小的来做分割点（这样留给下一个区间的空间就越大），所以第一条分割线就是区间1结束的位置。
class Solution { public: static bool cmp(vector<int>&a,vector<int>&b) { return a[1]<b[1]; } int eraseOverlapIntervals(vector<vector<int>>& intervals) { int count=1; sort(intervals.begin(),intervals.end(),cmp); //右边界升序排序 int end=intervals[0][1]; //初始化 for(int i=1;i<intervals.size();i++) { if(end<=intervals[i][0]) //如果是单独区间 { end=intervals[i][1]; //右边界推进 count++; //数量加1 } } return intervals.size()-count; } };
二、划分字母区间
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表.
class Solution { public: vector<int> partitionLabels(string s) { int hash[27]={0}; vector<int>res; for(int i=0;i<s.size();i++) { hash[s[i]-'a']=i; //哈希记录字母出现的最远的值 } int right=0; int left=0; for(int i=0;i<s.size();i++) { right=max(right,hash[s[i]-'a']); //right记录当前字母区间的最远值 if(i==right) //相等的时候就是找到了当前字母区间最远值 { res.push_back(right-left+1); //保存长度 left=right+1; //更新起始位置 } } return res; } };
三、合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
class Solution { public: static bool cmp(vector<int>&a,vector<int>&b) { return a[0]<b[0]; } vector<vector<int>> merge(vector<vector<int>>& intervals) { if(intervals.size()==1||intervals.size()==0) { return intervals; } sort(intervals.begin(),intervals.end(),cmp); //右边界排序 int right=intervals[0][1]; //初始化 int left=intervals[0][0]; int flag=0; vector<vector<int>> res; vector<int>path; for(int i=1;i<intervals.size();i++) { flag=0; while(i<intervals.size()&&right>=intervals[i][0]) //右边界关系 { right=max(right,intervals[i][1]); //更新区间 left=min(left,intervals[i][0]); i++; //直接跳下一个 } res.push_back({left,right}); //插入 if(i<intervals.size()) //准备退出辽 { left=intervals[i][0]; //最后记录一波 right=intervals[i][1]; flag=1; //记下标志 } } if(flag) res.push_back({left,right}); //插入，否则会漏一个 return res; } };
总结
1、关键是记录单个区间的值，右边界排序后，删最小右边界，右边会有更大空间。
2、用哈希来记录最长延长距离
3、排序后，分清记录值。
