FOJ 190. Coloring Intervals

Algorithm

競程作業，2017 TOPC Problem C：FOJ-190

他說有個人想要用高級方法塗顏色，互相重疊的區間不能是同一個顏色
然後問說最少需要用到幾種顏色

稍微畫一下下就會發現只要看最多區間的時刻是幾個區間就好了
所以區間 [a, b] 就換成兩個 pair: (a, -1), (b, 1)，a 設成 -1是因為等一下 sort 比較方便
然後把全部都丟進 vector 裡面 sort 在跑一次 整個 vector 就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<long long int, long long int> > V;
int main(){
  int t, n, big, ans;
  cin>>t;
  while(t--){
    V.clear();
    big = ans = 0;
    cin>>n;
    for(int i=0; i<n; i++){
      pair<long long int, long long int> p1, p2;
      cin>>p1.first>>p2.first;
      p1.second = -1;
      p2.second = 1;
      V.push_back(p1);
      V.push_back(p2);
    }
    sort(V.begin(), V.end());
    for(auto& it: V){
      ans -= it.second;
      if(ans>big) big = ans;
    }
    cout<<big<<"\n";
  }
}