โปรแกรม C++ หาจำนวนกลุ่มนักเขียนโปรแกรมที่จัดได้น้อยที่สุด

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A n องค์ประกอบ A[i] แทนทักษะการเขียนโปรแกรมของนักศึกษาคนที่ i ทุกค่าใน A ต่างกัน ต้องการแบ่งเป็นทีมที่:

• ไม่มีนักศึกษา i และ j ที่ |A[i] - A[j]| = 1 อยู่ในทีมเดียวกัน
• จำนวนทีมน้อยที่สุด

ขั้นตอนการแก้ปัญหา

dem := 1
เรียงลำดับ A
สำหรับ i := 1 ถึง ขนาด A - 1:
    ถ้า A[i] - A[i-1] == 1:
        dem := 2
คืนค่า dem

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

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

int solve(vector<int> A) {
    int dem = 1;
    sort(A.begin(), A.end());
    for (int i = 1; i < A.size(); i++)
        if (A[i] - A[i - 1] == 1)
            dem = 2;
    return dem;
}

int main() {
    vector<int> A = { 2, 3, 4, 99, 100 };
    cout << solve(A) << endl;
}

อินพุต

{ 2, 3, 4, 99, 100 }

เอาต์พุต

2