狗家电面

一道题给两个人的interval list. （

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

分。不知道lc上有没有这道题。

vector<pair<int, int>> overLap(vector<pair<int, int>>& a, vector<pair<int, int>>& b){

        map<int, unordered_map<char, int>> mp;

        sort(a.begin(), a.end());

        sort(b.begin(), b.end());

        for(auto it:a){

                mp[it.first]['a']++;

                mp[it.second]['a']--;

        }

        for(auto it:b){

                mp[it.first]['b']++;

                mp[it.second]['b']--;

        }

        vector<pair<int, int>> res;

        int start = -1;

        unordered_map<char, int> cur;

        for(auto it:mp){

                cur['a'] += it.second['a'];

                cur['b'] += it.second['b'];

                if(cur['a'] > 0 && cur['b'] == 0) start = it.first;

                if(cur['a'] == 0 || (cur['a'] > 0 && cur['b'] > 0 && start != -1)){

                        if(start != -1)

                        res.push_back(make_pair(start, it.first));

                        start = -1;

                }

        }

        return res;

}

用线扫描 保存两个人在每个端点的interval数量即可 （代码默认 interval 左边inclusive, 右边exclusive）

补充内容 (2018-3-19 06:27):
if(cur['a'] > 0 && cur['b'] == 0) start = it.first; 这行应该是  if(cur['a'] > 0 && cur['b'] == 0 && start == -1)

anywho 发表于 2018-3-19 06:25
vector overLap(vector& a, vector& b){        map mp;        sort(a.begin(), a.end());        sort(b.begin(), b.end());         ...

请问下能否解释一下你的做法？

先merge自己的interval，确保自己没有重叠，然后在混一起sort？