C++ 貪心問題、區間分組(含問題分析與代碼）

題目 AcWing906.區間分組

原題連結

描述

給定 N N N 個閉區間 [ a i , b i ] [ai,bi] [ai,bi]，請你将這些區間分成若幹組，使得每組内部的區間兩兩之間（包括端點）沒有交集，并使得組數盡可能小。

輸出最小組數。

輸入

第一行包含整數 N N N，表示區間數。

接下來 N N N​ 行，每行包含兩個整數 a i , b i ai,bi ai,bi，表示一個區間的兩個端點。

輸出

輸出一個整數，表示最小組數。

資料範圍

1 ≤ N ≤ 1 0 5 1≤N≤10^{5} 1≤N≤105

− 1 0 9 ≤ a i ≤ b i ≤ 1 0 9 −10^{9}≤ai≤bi≤10^{9} −109≤ai≤bi≤109

樣例輸入

3
-1 1
2 4
3 5
           

樣例輸出

2
           

思路

這道題用到一個很重要的資料結構

priority_queue

，需要包含頭檔案

<queue>

。優先隊列具有隊列的所有特性，包括隊列的基本操作，隻是在這基礎上添加了内部的一個排序，它本質是一個堆實作的。

優先權隊列有以下基本操作:

• top 通路隊頭元素
• empty 隊列是否為空
• size 傳回隊列内元素個數
• push 插入元素到隊尾 (并排序)
• emplace 原地構造一個元素并插入隊列
• pop 彈出隊頭元素
• swap 交換内容

定義：

priority_queue<Type, Container, Functional> heap;

Type 就是資料類型，Container 就是容器類型（Container必須是用數組實作的容器，比如

vector,deque

等等，但不能用 list。STL裡面預設用的是

vector

），Functional 就是比較的方式。當需要用自定義的資料類型時才需要傳入這三個參數，使用基本資料類型時，隻需要傳入資料類型，預設是大頂堆。一般定義方式為：

1 //升序隊列，小頂堆
2 priority_queue <int, vector<int>, greater<int>> heap;
3 //降序隊列，大頂堆
4 priority_queue <int, vector<int>, less<int>> heap;
           

本道題的貪心準則：按照區間左端點從小到大排序。

struct Range
{
    int l, r;
    bool operator<(const Range& R)const
    {
        return l < R.l;
    }
}range[N];
           

核心代碼分析

我們按左端點從小到大周遊，再将每個區間的左端點

range[i].l

與每一組的最右端點的最小值

heap.top()

比較：

若

heap.top() >= range[i].l

或

heap

為空，則說明沒有一組集合可以包含該區間，是以建立新的分組

heap.push(range[i].r)

；

若

heap.top() < range[i].l

，說明有分組可以包含該區間，我們預設把該區間加入到第一個分組中（第一個分組的右端點值較小，這樣可以使每個分組包含盡量多的區間），然後從

heap

中彈出第一個分組的右端點值，并用

range[i].r

更新第一個分組的右端點。

代碼

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
struct Range
{
    int l, r;
    bool operator<(const Range& R)const
    {
        return l < R.l;
    }
}range[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &range[i].l, &range[i].r);    
    sort(range, range + n);//将區間數組按左端點從小到大排序    
    int res = 0;
    //定義小根堆，用來存放每一組區間的最右端點
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i++)
    {
        if (heap.empty() || heap.top() >= range[i].l)
        {
            res++;//建立新的分組
            heap.push(range[i].r);
        }
        else
        {
            //彈出第一組右端點的值并更新
            heap.pop();
            heap.push(range[i].r);
        }
    }
    printf("%d", res);
    return 0;
}
           

歡迎交流與指正~