คนที่รายการบริษัทโปรดไม่ใช่ Subset ของอีกคนใน C++

สมมติว่าเรามีอาร์เรย์ favoriteCompanies โดย favoriteCompanies[i] คือรายการบริษัทโปรดของคนที่ i เราต้องหา index ของคนที่รายการของเขาไม่ใช่ subset ของรายการคนอื่นใดๆ

ตัวอย่าง: [[TCS,google,facebook], [google,microsoft], [google,facebook], [google], [amazon]] ผลลัพธ์ = [0,1,4]

วิธีแก้ปัญหา

1. เรียงรายการบริษัทของแต่ละคน
2. สำหรับแต่ละคน i ตรวจสอบกับทุกคน j (i≠j):
   • ใช้ two-pointer เช็คว่า f[i] เป็น subset ของ f[j] หรือไม่
   • ถ้าไม่ใช่ subset ของใครเลย ให้ใส่ i ในคำตอบ

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

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

void print_vector(vector<int> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 

class Solution { 
public: 
    bool ok(vector<string>& a, vector<string>& b){ 
        int cnt = 0, i = 0, j = 0; 
        while (i < a.size() && j < b.size()) { 
            if (a[i] == b[j]) { i++; j++; cnt++; } 
            else if (a[i] < b[j]) i++; 
            else j++; 
        } 
        return cnt < a.size(); 
    } 
    
    vector<int> peopleIndexes(vector<vector<string>>& f){ 
        set<int> s; 
        int n = f.size(); 
        for (int i = 0; i < n; i++) sort(f[i].begin(), f[i].end()); 
        for (int i = 0; i < n; i++) { 
            bool c = true; 
            for (int j = 0; j < n; j++) { 
                if (i == j) continue; 
                c &= ok(f[i], f[j]); 
            } 
            if (c) s.insert(i); 
        } 
        return vector<int>(s.begin(), s.end()); 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<string>> v = {{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}; 
    print_vector(ob.peopleIndexes(v)); 
}

ข้อมูลนำเข้า

{{"TCS","google","facebook"},{"google","microsoft"},{"google","facebook"},{"google"},{"amazon"}}

ผลลัพธ์

[0, 1, 4, ]