LiveArchive 5864 - Register Allocation

問題概要

N個の変数があり、それぞれの変数は[s_i,f_i]の期間でレジスタに割り当てられる。[s_i,f_i]∩[s_j,f_j]=Φならば同じレジスタを使うことができる。この条件の下で使用するレジスタの個数を最小化せよ。

制約

• 1 ≤ N ≤ 10000
• 1 ≤ s_i ≤ 10000
• 2 ≤ f_i ≤ 30000

解法

imos法。

コード

#include <bits/stdc++.h>

using namespace std;

#define MAX 30010

int main(){
  int Tc,N;
  cin >> Tc;
  while(Tc--){
    int a[MAX]={0};
    cin >> N;
    for(int i = 0 ; i < N ; i++){
      int s,t;
      cin >> s >> t;
      a[s]++; a[t+1]--;
    }
    int res = 0;
    for(int i = 1 ; i < MAX ; i++){
      a[i] += a[i-1];
      res = max(res,a[i]);
    }
    cout << res << endl;
  }
  return 0;
}