SMH
InterviewTime limit1sMemory limit512 MB
Given heights of up to 11 students in a line, find the maximum number of other students any single student can see, where sight is blocked by any head on the segment.
- Level
Medium4 of 10
- Topics
- Brute force, Geometry, Array, Implementation
- Solved
- No attempts yet
Problem
Write a function P5:
- Samin High School has N students in the class of '20. The principal has bad memories involving students whose heights are similar to his own, so he admitted every student with a distinct height (student IDs are not sorted by height).
- One day, the students lined up in a single straight line on the school field for a health checkup. The spacing between adjacent students is 1 m.
- The teacher wants to secretly watch the students and picks one of them to act as a lookout. Since the students stand in a straight line, a student cannot see anyone blocked by their line of sight. For example, if the students in order have heights 1 m, 3 m, and 2 m, the 1 m student cannot see the 2 m student.
- It is not true that a student can always see a taller student or can never see a shorter one. Draw the students on a plane and connect the heads of two different students: one can see the other if there is no obstacle on the line segment. If a head lies on the line segment, they cannot see each other.
- The teacher wants to select the student who can watch as many students as possible.
- input parameter: a list A stores each student's height in meters as an integer, ordered by student ID. A[] represents student 20- (e.g.: A[0] → 20-001). Heights range from 1 m to 100 m. The size of list A is at most 11.
- return value: return the maximum number of students that can be watched.