划分字母区间(美团真题)

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

示例 1:

输入: S = "ababcbacadefegdehijhklij"
输出: [9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

注意:

S的长度在[1, 500]之间。
S只包含小写字母'a'到'z'。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-labels
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
（1）遍历整个输入的字符串，找到每一个字符对应的最小的起点以及最大的终点index；leetcode的编译器是clang，unordered_map的顺序和输入顺序是不一致的，在g++上应该是一致，因此后面有单独对这个unordered_map转化为了vector进行排序操作；
（2）第二部分就是范围的划分问题，如果两个范围存在交集则更新两个范围并集的起始点和结束点；如果不存在交集则表示可以划分区域来计算长度；

class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }

    vector<int> partitionLabels(string S) {
        unordered_map<char, pair<int, int>> _map;
        for (int i = 0; i < S.size(); ++i) {
            if (_map.find(S[i]) == _map.end()) {
                _map[S[i]] = make_pair(i, i);
            }
            else {
                int start = _map[S[i]].first;
                int end = _map[S[i]].second;
                if (i < start)
                    _map[S[i]].first = i;
                if (i > end)
                    _map[S[i]].second = i;
            }
        }
        vector<vector<int>> map_vec;
        for(unordered_map<char, pair<int,int>>::iterator iter = _map.begin(); iter != _map.end(); ++iter) {
            map_vec.push_back({iter->second.first, iter->second.second});
        }
        sort(map_vec.begin(), map_vec.end(), cmp);
        vector<int> vec;
        int start = -1, end = -1;
        for(int i = 0; i < map_vec.size(); ++i) {
            if(start == -1 && end == -1) {
                // 表示初始化
                start = map_vec[i][0];
                end = map_vec[i][1];
            } else {
                if(map_vec[i][0] > end) {
                    vec.push_back(end - start + 1);
                    start = map_vec[i][0];
                    end = map_vec[i][1];
                    continue;
                } else if(map_vec[i][0] < start && map_vec[i][1] > end) {
                    start = map_vec[i][0];
                    end = map_vec[i][1];
                    continue;
                } else if(map_vec[i][0] < end && map_vec[i][0] > start && map_vec[i][1] > end) {
                    end = map_vec[i][1];
                }
            }
        }
        vec.push_back(end - start + 1);
        return vec;
    }
};