PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Sorting, longest increasing subsequence
PROBLEM:
You’re given N intervals [L_i, R_i].
Create a graph on N vertices with an edge between vertices i, j if and only if [L_i, R_i] and [L_j, R_j] both contain a real number not contained in the other one.
Find the maximum clique in such a graph.
EXPLANATION:
For two intervals [a, b] and [c, d], it can be seen that [a, b] contains some point that [c, d] doesn’t if and only if [a, b] is not fully contained in [c, d], i.e, either a\lt c or b\gt d holds.
In our case, there’s an edge between two intervals when both of them contain some point not in the other.
That means there’s an edge between each pair of intervals which don’t satisfy the containment relation in either direction.
Now, let’s see what it means for some intervals to form a clique under this relation.
Suppose intervals [l_1, r_1], [l_2, r_2],\ldots, [l_k, r_k] form a clique.
For convenience, let’s order these intervals so that l_1 \lt l_2 \lt \ldots\lt l_k.
Then,
- [l_2, r_2] is not fully contained in [l_1, r_1].
Since l_2 \gt l_1, this means r_2 \gt r_1 must hold. - [l_3, r_3] is not fully contained in [l_2, r_2].
Again, since l_3\gt l_2, we must have r_3\gt r_2. - This applies to every i \gt 1 in fact: r_i \gt r_{i-1} must hold.
In other words, when looking at the intervals in ascending orders of their left endpoints, we find that their right endpoints also end up being in ascending order.
It’s not not hard to see that this condition is not just necessary, but also sufficient.
That is, we have
Lemma: The set of intervals [l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k], where l_1 \lt l_2 \lt\ldots\lt l_k, forms a clique if and only if r_1 \lt r_2 \lt\ldots\lt r_k.
With this in hand, let’s move to computing the largest clique.
Let’s sort all intervals in ascending order of their left endpoints.
Then, we want to find the largest subset of intervals such that their right endpoints are in increasing order when viewed from left to right.
This is exactly the longest increasing subsequence problem on the right endpoints!
So, all that needs to be done is compute the LIS of the right endpoints after sorting, which is doable in \mathcal{O}(N\log N) in several ways: generally, dynamic programming that can be optimized either using some point update + range max query data structure (like a segment tree), or binary search.
You can read this article if the concept is new to you.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct segtree{
struct node{
int x = 0;
void apply(int l, int r, int y){
x = max(x, y);
}
};
int n;
vector <node> seg;
node unite(node a, node b){
node res;
res.x = max(a.x, b.x);
return res;
}
void push(int l, int r, int pos){
}
void pull(int pos){
seg[pos] = unite(seg[pos * 2], seg[pos * 2 + 1]);
}
void build(int l, int r, int pos){
if (l == r){
return;
}
int mid = (l + r) / 2;
build(l, mid, pos * 2);
build(mid + 1, r, pos * 2 + 1);
pull(pos);
}
template<typename M>
void build(int l, int r, int pos, vector<M> &v){
if (l == r){
seg[pos].apply(l, r, v[l]);
return;
}
int mid = (l + r) / 2;
build(l, mid, pos * 2, v);
build(mid + 1, r, pos * 2 + 1, v);
pull(pos);
}
node query(int l, int r, int pos, int ql, int qr){
push(l, r, pos);
if (l >= ql && r <= qr){
return seg[pos];
}
int mid = (l + r) / 2;
node res{};
if (qr <= mid) res = query(l, mid, pos * 2, ql, qr);
else if (ql > mid) res = query(mid + 1, r, pos * 2 + 1, ql, qr);
else res = unite(query(l, mid, pos * 2, ql, qr), query(mid + 1, r, pos * 2 + 1, ql, qr));
pull(pos);
return res;
}
template <typename... M>
void modify(int l, int r, int pos, int ql, int qr, M&... v){
push(l, r, pos);
if (l >= ql && r <= qr){
seg[pos].apply(l, r, v...);
return;
}
int mid = (l + r) / 2;
if (ql <= mid) modify(l, mid, pos * 2, ql, qr, v...);
if (qr > mid) modify(mid + 1, r, pos * 2 + 1, ql, qr, v...);
pull(pos);
}
segtree (int _n){
n = _n;
seg.resize(4 * n + 1);
build(1, n, 1);
}
template <typename M>
segtree (int _n, vector<M> &v){
n = _n;
seg.resize(4 * n + 1);
if (v.size() == n){
v.insert(v.begin(), M());
}
build(1, n, 1, v);
}
node query(int l, int r){
return query(1, n, 1, l, r);
}
node query(int x){
return query(1, n, 1, x, x);
}
template <typename... M>
void modify(int ql, int qr, M&...v){
modify(1, n, 1, ql, qr, v...);
}
};
void Solve()
{
int n; cin >> n;
vector <pair<int, int>> a(n);
vector <int> r(2 * n + 1, -1);
for (auto &[x, y] : a){
cin >> x >> y;
r[x] = y;
}
// dp[j] = furthest to right covered
// when we get a new interval [l, r]
// furthest covered < r must be satisfied
// and we will update furthest covered = r
// range max query
segtree seg(2 * n);
int ans = 0;
for (int i = 1; i <= 2 * n; i++){
if (r[i] != -1){
int v = seg.query(1, r[i] - 1).x + 1;
ans = max(ans, v);
seg.modify(r[i], r[i], v);
}
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
template<typename T>
struct segtree {
// https://codeforces.com/blog/entry/18051
/*=======================================================*/
struct data {
ll a;
};
data neutral = {0};
data merge(data &left, data &right) {
data curr;
curr.a = max(left.a,right.a);
return curr;
}
void create(int i, T v) {
}
void modify(int i, T v) {
tr[i].a = v;
}
/*=======================================================*/
int n;
vector<data> tr;
segtree() {
}
segtree(int siz) {
init(siz);
}
void init(int siz) {
n = siz;
tr.assign(2 * n, neutral);
}
void build(vector<T> &a, int siz) {
rep(i, siz) create(i + n, a[i]);
rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
void pupd(int i, T v) {
modify(i + n, v);
for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
}
data query(int l, int r) {
data resl = neutral, resr = neutral;
for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
if (l & 1) resl = merge(resl, tr[l++]);
if (!(r & 1)) resr = merge(tr[r--], resr);
}
return merge(resl, resr);
}
};
void solve(int test_case)
{
ll n; cin >> n;
vector<pll> a(n+5);
rep1(i,n) cin >> a[i].ss >> a[i].ff;
sort(a.begin()+1,a.begin()+n+1);
vector<ll> lis;
rep1(i,n){
auto [r,l] = a[i];
auto it = upper_bound(all(lis),l);
if(it == lis.end()) lis.pb(l);
else *it = l;
}
ll ans = sz(lis);
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/lis.py
def lis(nums, cmp=lambda x, y: x < y):
P = [0] * len(nums)
M = [0] * (len(nums) + 1)
L = 0
for i in range(len(nums)):
lo, hi = 1, L
while lo <= hi:
mid = (lo + hi) // 2
if cmp(nums[M[mid]], nums[i]):
lo = mid + 1
else:
hi = mid - 1
newL = lo
P[i] = M[newL - 1]
M[newL] = i
L = max(L, newL)
S = [0] * L
k = M[L]
for i in range(L - 1, -1, -1):
S[i], k = nums[k], P[k]
return S
for _ in range(int(input())):
n = int(input())
intervals = []
for i in range(n):
L, R = map(int, input().split())
intervals.append((L, R))
intervals.sort()
pts = [intervals[i][1] for i in range(n) ]
print(len(lis(pts)))
, i was thinking more along the line of using stack cause of this.