You are given an array A representing heights of students. All the students are

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.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.