โปรแกรม C++ นับจำนวนเมืองที่เดินทางได้จากแต่ละเมือง

กำหนดให้มีรายการพิกัด N จุด P ในรูปแบบ (xi, yi) โดยค่า x และ y เป็นการเรียงสับเปลี่ยน (permutation) ของจำนวนธรรมชาติ N ตัวแรก สำหรับแต่ละ k ตั้งแต่ 1 ถึง N เราอยู่ที่เมือง k สามารถทำการดำเนินการได้ไม่จำกัดครั้ง การดำเนินการ: ย้ายไปเมืองอื่นที่มีพิกัด x น้อยกว่าและ y น้อยกว่า หรือ x มากกว่าและ y มากกว่าเมืองปัจจุบัน ต้องการหาจำนวนเมืองที่สามารถไปถึงได้จากเมือง k

ตัวอย่าง

Input: P = [[1, 4], [2, 3], [3, 1], [4, 2]]
Output: [1, 1, 2, 2]

อัลกอริทึม

1. สร้างอาร์เรย์ 2 มิติ lst เก็บ {x, y, index} และเรียงตาม x
2. ใช้ตัวแปร y_min ติดตามค่า y ต่ำสุดที่เจอมา
3. ใช้ Set se เก็บ index ของเมืองในกลุ่มปัจจุบัน
4. เมื่อ y_min + i == n แสดงว่าจบกลุ่มหนึ่ง กำหนดคำตอบให้ทุกเมืองในกลุ่ม = ขนาดของกลุ่ม
5. ล้าง Set และต่อไปกลุ่มถัดไป

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

void solve(vector<vector<int>> P) {
    int n = P.size();
    vector<vector<int>> lst;
    
    for (int i = 0; i < n; i++) {
        vector<int> v = { P[i][0], P[i][1], i };
        lst.push_back(v);
    }
    sort(lst.begin(), lst.end());
    
    int y_min = 1e9;
    set<int> se;
    vector<int> ans(n, 0);
    
    for (int i = 0; i < n; i++) {
        y_min = min(y_min, lst[i][1]);
        se.insert(lst[i][2]);
        
        if (y_min + i == n) {
            for (auto j : se)
                ans[j] = se.size();
            se.clear();
        }
        if (i == n - 1) {
            for (auto j : se)
                ans[j] = se.size();
        }
    }
    
    for (int i = 0; i < n; i++)
        cout << ans[i] << ", ";
}

int main() {
    vector<vector<int>> P = { { 1, 4 }, { 2, 3 }, { 3, 1 }, { 4, 2 } };
    solve(P);
}

ผลลัพธ์

1, 1, 2, 2,