You are given an array A representing heights of students. All the students are
ID: 3752656 • Letter: Y
Question
You are given an array A representing heights of students. All the students are asked to stand in rows. The students arrive by one, sequentially (as their heights appear in A). For the i-th student, if there is a row in which all the students are taller than Alil, the student will stand in one of such rows. If there is no such row, the student will create a new row. Your task is to find the minimum number of rows created. Write a function: int solution(vector &A); that, given a non-empty array A containing N integers, denoting the heights of the students, returns the minimum number of rows created For example, given A-[5,4, 3, 6, 1], the function should return 2 Students will arrive in sequential order from AlO] to AIN-1]. So, the first student will have height 5, the second student will have height = 4, and so on. For the first student, there is no row, so the student will create a new row Row1[5]Explanation / Answer
int solution(vector<int> &A) {
int n = A.size();
int i,j;
vector<int> rows;
for(i=0;i<n;i++) {
int cur = A[i];
int flag = 0;
int idx;
int max = 100000000;
for(j=0;j<rows.size();j++) {
if(cur<A[j] && A[j]-cur<max) {
flag = 1;
idx = j;
max = A[j]-cur;
}
}
if(flag) A[idx] = cur;
else rows.push_back(cur);
}
return rows.size();
}
Store minimum of each row in rows vector. Now assign current student to a row if his height is less than the minimum and the difference between these 2 heights is minimum. The second condition is used because it is optimal. A student with very less height will only block the row where difference is less between his height and minimum of row, thus allowing greater height student to fill other rows.