Cho mảng A kích thước n, A[i] là kỹ năng lập trình (phân biệt). Chia thành nhóm sao cho: không có 2 người chênh lệch kỹ năng 1 trong cùng nhóm, số nhóm tối thiểu.
Ví dụ
Với A=[2,3,4,99,100], đầu ra 2. Nhóm 1: [2,3,4], nhóm 2: [99,100].
Giải thuật
Sắp xếp A. Nếu tồn tại cặp liền kề chênh lệch 1 (A[i] - A[i-1] == 1), cần 2 nhóm. Ngược lại 1 nhóm. Vì chỉ có 2 nhóm tối đa (gán chẵn/lẻ theo giá trị).
Mã 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;
}
Đầu vào / Đầu ra
Input: { 2, 3, 4, 99, 100 }
Output: 2