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

// ชุดย่อย N <= 3,000: ตรรกะช่องว่างเหมือนตัวเต็มทุกบรรทัด ต่างกันแค่ cnt ที่ไล่งานทีละตัว
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> byEnd;          // (วันจบ, วันเริ่ม) เรียงตามวันจบ

// ท่าโลภ: ไล่งานตามวันจบ หยิบทุกตัวที่อยู่ในช่วงและเริ่มหลังตัวที่หยิบล่าสุด
int cnt(int l, int r){
    int cur = l - 1, res = 0;
    for(auto [en, st] : byEnd){
        if(en > r) break;
        if(st > cur){ cur = en; res++; }
        // st >= l เป็นจริงเองเมื่อ st > cur เพราะ cur เริ่มที่ l - 1
    }
    return res;
}

int main(){
    int n;
    if(scanf("%d", &n) != 1) return 0;
    vector<int> s(n), e(n);
    for(int i = 0; i < n; i++) if(scanf("%d %d", &s[i], &e[i]) != 2) return 0;
    for(int i = 0; i < n; i++) byEnd.push_back({e[i], s[i]});
    sort(byEnd.begin(), byEnd.end());

    const int LO = 1, HI = 1000000000;
    int total = cnt(LO, HI);
    map<int, pair<int,int>> gaps;     // วันเริ่มช่องว่าง -> (วันจบช่องว่าง, วางได้กี่งาน)
    gaps[LO] = {HI, total};
    vector<int> chosen;
    for(int i = 0; i < n && (int)chosen.size() < total; i++){
        auto it = gaps.upper_bound(s[i]);
        if(it == gaps.begin()) continue;
        --it;
        int gl = it->first, gr = it->second.first, c = it->second.second;
        if(e[i] > gr) continue;                                  // คร่อมงานที่รับไปแล้ว
        int c1 = cnt(gl, s[i] - 1), c2 = cnt(e[i] + 1, gr);
        if(c1 + 1 + c2 != c) continue;                           // รับแล้วช่องว่างนี้เสียจำนวน
        gaps.erase(it);
        if(gl <= s[i] - 1) gaps[gl] = {s[i] - 1, c1};
        if(e[i] + 1 <= gr) gaps[e[i] + 1] = {gr, c2};
        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;

const int LOG = 18;                   // 2^18 = 262,144 มากกว่า N ที่มากที่สุด
const int NONE = INT_MAX;             // ไปต่อไม่ได้ ตั้งเป็นค่าใหญ่สุดเพื่อให้ตกการเทียบ q <= lim เอง
vector<int> xs;                       // พิกัดที่การนับไปยืนได้: วันที่ 1 และวันจบ + 1 ของทุกงาน
vector<array<int, LOG>> up;           // up[i][k] = กระโดด 2^k ก้าวจากพิกัด i แล้วไปถึงพิกัดไหน
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), res = 0;
    int lim = (int)(upper_bound(xs.begin(), xs.end(), r + 1) - xs.begin()) - 1;  // พิกัดสุดท้ายที่ไม่เกิน r + 1
    for(int k = LOG - 1; k >= 0; k--){
        int q = up[cur][k];
        if(q <= lim){ res += 1 << k; cur = q; }   // ก้าวนี้ยังไม่เลยขอบขวา ก้าวได้
    }
    return res;
}

int main(){
    int n;
    if(scanf("%d", &n) != 1) return 0;
    vector<int> s(n), e(n);
    for(int i = 0; i < n; i++) if(scanf("%d %d", &s[i], &e[i]) != 2) return 0;

    // ---- บีบพิกัด: ไม่ต้องเก็บวันเริ่ม เพราะการนับไม่เคยไปยืนที่วันเริ่ม ----
    xs.reserve(n + 2);
    for(int i = 0; i < n; 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());
    int m = (int)xs.size();

    // ---- ก้าวเดียว: จากพิกัด i หยิบงานที่เริ่มไม่ก่อน xs[i] และจบเร็วที่สุด แล้วไปต่อที่วันจบ + 1 ----
    vector<pair<int,int>> byStart(n);
    for(int i = 0; i < n; i++) byStart[i] = {s[i], e[i]};
    sort(byStart.begin(), byStart.end());
    up.assign(m, {});
    int best = INT_MAX, j = n - 1;
    for(int i = m - 1; i >= 0; i--){
        while(j >= 0 && byStart[j].first >= xs[i]){ best = min(best, byStart[j].second); j--; }
        up[i][0] = (best == INT_MAX) ? NONE : idxOf(best + 1);
    }

    // ---- ตารางกระโดด: 2^k ก้าว = 2^(k-1) ก้าว สองรอบ ----
    for(int k = 1; k < LOG; k++) for(int i = 0; i < m; i++){
        int q = up[i][k - 1];
        up[i][k] = (q == NONE) ? NONE : up[q][k - 1];
    }

    // ---- ไล่ตามหมายเลข: ช่องว่างแต่ละช่องจำไว้ว่าวางได้กี่งาน ----
    const int LO = 1, HI = 1000000000;
    int total = cnt(LO, HI);
    map<int, pair<int,int>> gaps;     // วันเริ่มช่องว่าง -> (วันจบช่องว่าง, วางได้กี่งาน)
    gaps[LO] = {HI, total};
    vector<int> chosen;
    for(int i = 0; i < n && (int)chosen.size() < total; i++){
        auto it = gaps.upper_bound(s[i]);
        if(it == gaps.begin()) continue;
        --it;
        int gl = it->first, gr = it->second.first, c = it->second.second;
        if(e[i] > gr) continue;                                  // คร่อมงานที่รับไปแล้ว
        int c1 = cnt(gl, s[i] - 1), c2 = cnt(e[i] + 1, gr);
        if(c1 + 1 + c2 != c) continue;                           // รับแล้วช่องว่างนี้เสียจำนวน
        gaps.erase(it);
        if(gl <= s[i] - 1) gaps[gl] = {s[i] - 1, c1};
        if(e[i] + 1 <= gr) gaps[e[i] + 1] = {gr, c2};
        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");
}