Quietest Person Among All Who Are At Least As Rich
Given partial 'richer than' relations and a quietness score per person, for each person find the quietest individual among everyone known to be at least as rich as them (including themselves).
Problem
There are n people (0..n-1). richer[i] = [a, b] means person a is richer than person b. quiet[i] is the quietness of person i (all quiet values distinct). Return an array answer where answer[x] is the index of the least-quiet (smallest quiet value) person among all people who are definitely at least as rich as x (x included).
Input
A list richer of [a, b] richer-than pairs and an array quiet.
Output
An array answer of person indices.
Constraints
- 1 <= n <= 500
- 0 <= richer.length <= n*(n-1)/2
- The richer relation is a DAG; quiet is a permutation of 0..n-1.
Examples
Example 1
Input
richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output
[5,5,2,5,4,5,6,7]
For person 0, the quietest richer-or-equal person is index 5.
Example 2
Input
richer = [], quiet = [0]
Output
[0]
A single person answers themselves.