2022-08-17-nvidia实习

逐个插入区间，合并区间，最后返回无重复的一个或多个区间

#include
#include

using namespace std;

#define pii pair

class MergeIntervals{
private:
    vector intervals;
    vector::iterator mergeNext(vector::iterator p){
        while(next(p)!=intervals.end()&&p->second>=next(p)->first){
            p->second=next(p).second;
            intervals.erase(p+1);
        }
        return p;
    }

public:
    void test(pii v){
        auto lb = lower_bound(internals.begin(),intervals.end(),v); // >= v.first

        // merge last
        auto preInterval = prev(lb);
        if(preInterval && preInterval.second>=v.second){
            return;
        }

        // insert new pair to next
        lb.insert(v); // lb v ...
        auto p = lb;
        p = mergeNext(p); // merge lb and its next: lb.second >= v.first

        if(p==intervals.end()||next(p)==intervals.end()) // no next or p is the last
            return;

        p=p+1;
        mergeNext(p); // merge v and its next: lb.second < v.first
        return;
    }

    vector callHistory(){
        return intervals;
    }
};

int main()
{

    return 0;
}

感觉数据结构用错了，vector插入太慢了，以前(好像是去年下半年)做过一个leetcode每日一题也是这个
找不到了

当时记录4种语言语法就花了许久功夫，上面是java的（应该只有第一部分）

// 后来发现一大堆错误，除了大致的大致的思路没错，其他全是错的，前面后面全错了！！！
// 面试官完全没发现，还给予了一定的肯定。
// 写了个测试用例，自己调出来了，可能还有错
// 其实还是O(n*n)的，完全可以先把n个区间全存起来最后再排序去重...


#include <iostream>
#include <vector>

using namespace std;

#define pii pair<int, int>

class MergeIntervals
{
private:
    vector<pii> intervals;
    vector<pii>::iterator mergeNext(vector<pii>::iterator p)
    {
        while (next(p) != intervals.end() && p->second >= next(p)->first)
        {
            p->second = max(p->second, next(p)->second);
            intervals.erase(p + 1);
        }
        return p;
    }

public:
    void test(pii v)
    {
        if (intervals.size() == 0)
        {
            intervals.push_back(v);
            return;
        }

        auto lb = lower_bound(intervals.begin(), intervals.end(), v); // >= v.first

        // merge last
        if (lb != intervals.begin())
        {
            auto preInterval = prev(lb);
            if (preInterval->second >= v.second)
                return;
            else if(preInterval->second>=v.first){
                preInterval->second = max(preInterval->second, v.second);
                mergeNext(preInterval);
                return;
            }
        }

        // insert new pair to next
        vector<pii>::iterator w;
        if (lb == intervals.end())
        {
            w = intervals.insert(lb, v);
            // cout << w->first << ", " << w->second << "\n";
            return;
        }
        else{
            w = intervals.insert(lb, v); // w(v) lb ...
            // cout << w->first << ", " << w->second << "\n";
        }

        auto p = w;
        p = mergeNext(p); // merge w and its next: w.second >= lb.first

        // if (p == intervals.end() || next(p) == intervals.end()) // no next or p is the last
        //     return;

        // p = p + 1;
        // mergeNext(p); // merge w and its next: w.second < lb.first
        return;
    }

    vector<pii> callHistory()
    {
        return intervals;
    }
};

int main()
{
    MergeIntervals m;
    pii p = make_pair<int, int>(1, 10);
    m.test(pair<int, int>(1, 10));
    m.test(make_pair(10, 15));
    m.test(make_pair(17, 20));
    m.test(make_pair(13, 30));
    m.test(make_pair(40, 50));
    m.test(make_pair(27, 40));

    vector<pii> h = m.callHistory();
    for (auto i : h)
    {
        cout << i.first << ", " << i.second << "\n";
    }
    return 0;
}