ห้องประชุมเมืองสิรุเสรี: จำนวนมากที่สุดเป็นแค่ครึ่งเดียวของโจทย์

#include <bits/stdc++.h>
using namespace std;
int n, m_, LOG;
vector<int> xs;                       // พิกัดวันที่ถูกบีบแล้ว
vector<vector<int>> up;               // up[k][i] = ดัชนีพิกัดหลังกระโดด 2^k ครั้ง
const int NONE = -1;
inline int idxOf(int v){ return (int)(lower_bound(xs.begin(), xs.end(), v) - xs.begin()); }

// จำนวนงานที่ไม่ทับกันมากที่สุด ที่วางได้ทั้งก้อนในช่วงวัน [l, r]
int cnt(int l, int r){
    if(l > r) return 0;
    int cur = idxOf(l);               // พิกัดแรกที่ไม่ก่อน l
    if(cur >= m_) return 0;
    int res = 0;
    for(int k = LOG - 1; k >= 0; k--){
        int q = up[k][cur];
        if(q != NONE && xs[q] <= r + 1){ res += 1 << k; cur = q; }
    }
    return res;
}

int main(){
    if(scanf("%d", &n) != 1) return 0;
    vector<int> s(n), e(n);
    for(int i = 0; i < n; i++) scanf("%d %d", &s[i], &e[i]);
    xs.reserve(3 * n + 2);
    for(int i = 0; i < n; i++){ xs.push_back(s[i]); xs.push_back(e[i]); xs.push_back(e[i] + 1); }
    xs.push_back(1); xs.push_back(1000000001);
    sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
    m_ = (int)xs.size();

    // f[i] = วันจบที่น้อยที่สุด ในบรรดางานที่เริ่มไม่ก่อนพิกัด xs[i]
    vector<int> f(m_, INT_MAX);
    { vector<vector<int>> byStart(m_);
      for(int i = 0; i < n; i++) byStart[idxOf(s[i])].push_back(e[i]);
      int best = INT_MAX;
      for(int i = m_ - 1; i >= 0; i--){ for(int v : byStart[i]) best = min(best, v); f[i] = best; } }

    LOG = 1; while((1 << LOG) <= n) LOG++;
    up.assign(LOG, vector<int>(m_, NONE));
    for(int i = 0; i < m_; i++) if(f[i] != INT_MAX) up[0][i] = idxOf(f[i] + 1);
    for(int k = 1; k < LOG; k++) for(int i = 0; i < m_; i++){
        int q = up[k-1][i]; up[k][i] = (q == NONE) ? NONE : up[k-1][q]; }

    int LO = 1, HI = 1000000000;
    int total = cnt(LO, HI);

    // ไล่ตามหมายเลขบริษัท รับได้ก็รับ ตราบใดที่จำนวนรวมยังไม่ลด
    set<pair<int,int>> gaps; gaps.insert({LO, HI});
    vector<int> chosen;
    for(int i = 0; i < n && (int)chosen.size() < total; i++){
        auto it = gaps.upper_bound({s[i], INT_MAX});
        if(it == gaps.begin()) continue;
        --it;
        int gl = it->first, gr = it->second;
        if(s[i] < gl || e[i] > gr) continue;                  // คร่อมงานที่รับไปแล้ว
        if(cnt(gl, s[i] - 1) + 1 + cnt(e[i] + 1, gr) != cnt(gl, gr)) continue;
        gaps.erase(it);
        if(gl <= s[i] - 1) gaps.insert({gl, s[i] - 1});
        if(e[i] + 1 <= gr) gaps.insert({e[i] + 1, gr});
        chosen.push_back(i + 1);
    }
    printf("%d\n", total);
    for(size_t i = 0; i < chosen.size(); i++) printf("%d%c", chosen[i], i + 1 == chosen.size() ? '\n' : ' ');
    if(chosen.empty()) printf("\n");
}

// ตัวตรวจ ลองทุกเซตย่อย เอาเซตใหญ่ที่สุดที่เรียงแล้วเล็กที่สุดตามพจนานุกรม
// ไม่มีท่าโลภหรือตารางกระโดดอยู่ในนี้เลย
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; scanf("%d", &n); vector<int> s(n), e(n);
    for(int i = 0; i < n; i++) scanf("%d %d", &s[i], &e[i]);
    vector<int> best;
    for(int m = 0; m < (1 << n); m++){
        vector<int> id; bool ok = true;
        for(int i = 0; i < n; i++) if(m >> i & 1) id.push_back(i);
        for(size_t a = 0; a < id.size() && ok; a++) for(size_t b = a + 1; b < id.size() && ok; b++){
            int x = id[a], y = id[b]; if(!(e[x] < s[y] || e[y] < s[x])) ok = false; }
        if(!ok) continue;
        if(id.size() > best.size() || (id.size() == best.size() && id < best)) best = id;
    }
    printf("%d\n", (int)best.size());
    for(size_t i = 0; i < best.size(); i++) printf("%d%c", best[i] + 1, i + 1 == best.size() ? '\n' : ' ');
    if(best.empty()) printf("\n");
}