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 A[i], 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. test cases

Question

Zechariah Nielsen

Mathematics

7 April, 10:35

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 A[i], 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. test cases

+5

Answers (1)

Know the Answer?

Gunnar Meyers · Answer 1

The minimum number of rows is 1: if A is sorted in descending order, every next students will arrive in a row where everyone is taller than him, and no new rows will be created.

For example, consider

A = [190, 175, 170, 165, 150]

The first students creates the first row.

The second student is 175cm tall. In the first row everyone is taller than him (there's only the 190cm student), so he'll stand in this row.

The third student, 170cm, will find the row filled by the students who are 190 and 175cm tall. So, everyone is taller than him and he'll stand in that row as well.

You keep going with the other students, and you'll see that no one will form a new row.