算法基础之区间分组

2024-01-03 18:16:36

区间分组

  • 核心思想:贪心

    • 所有组中右端点最大值都比当前遍历的区间的左端点大 则需要开新组

    • 为了让组数最多 根据左端点排序

    •   #include<iostream>
        #include<algorithm>
        #include<queue>
        
        using namespace std;
        const int N = 100010;
        
        struct Range{
            int l,r;
            bool operator< (const Range &W)const{
                return l<W.l;  //左端点排序
            }
        }range[N];
        
        int main()
        {
            int n;
            cin>>n;
            for(int i=0;i<n;i++) cin>>range[i].l>>range[i].r;
            
            priority_queue<int , vector<int> , greater<int>> heap;  //小根堆 找最小右端点
            //heap中每一个位置相当于一个组 当需要让区间入组时 将该位置删掉 再加上
            sort(range,range+n);
            for(int i=0;i<n;i++)
            {
                auto r = range[i];  //当前遍历区间
                if(heap.empty() || heap.top() >= r.l) heap.push(r.r);  //空或最小右端点都比左端点大 则开新组
                else
                {
                    heap.pop();  //删掉这组中原来的
                    heap.push(r.r);  //把新的放进去 右端点会变大
                }
            }
            
            cout<<heap.size();  //有多少个元素就有多少组
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135367598
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。