#問題概要
問題のリンク
$N$ 枚の ID カードと $M$ 個のゲートがある。
$i$ 番目のゲートは $L_i,L_{i+1},...,R_i$ 番目の ID カードのうちどれか $1$ 枚を持っていれば通過できる。$1$ 枚だけで全てのゲートを通過できる ID カードは何枚あるか。
#制約条件
- 入力は全て整数である。
- $1≤N≤10^5$
- $1≤M≤10^5$
- $1≤L_i≤R_i≤N$
#考えたこと
$M$個の閉区間全てに共通する要素の個数を数え上げる問題。
実験すればわかるが、全ての区間が重なっているということは「最も左側にある右端」>=「最も右側にある左端」が成り立つ。(この問題は閉区間なので>=となる。)
よって、「最も左側にある右端」と「最も右側にある左端」を min
と max
で更新していき、右端-左端が正か負か判定します。正なら1を足し、負なら0が答え。
計算量は $O(M)$ です。
#解答
c.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; cin >> n >> m;
int r = n;
int l = 0;
for(int i = 0; i < m; i ++) {
int x,y; cin >> x >> y;
l = max(l,x);
r = min(r,y);
}
cout << (r-l>=0 ? r-l+1 : 0) << endl;
}