School Admission Cutoff Score Planner

MEDIUM20 pts

A university admissions platform receives annual exam distribution snapshots and must help each school publish a safe, data-backed eligibility cutoff.

Table: schools

school_id: unique identifier of a school
capacity: maximum number of applicants the school can absorb

Table: exam

score: unique exam score threshold
student_count: number of students who scored at least this score

Data guarantee:

The exam distribution is logically monotonic.
If score_a > score_b, then student_count_a <= student_count_b.

Task: For each school_id, choose a cutoff score from the exam table using these policy rules:

Safety rule: if every student meeting the cutoff applies, applications must not exceed capacity.
Reach rule: among safe cutoffs, maximize the number of eligible applicants.
Tie-break rule: if multiple cutoffs produce the same maximum reach, return the smallest score.
If no cutoff can satisfy safety, return -1.

Output requirements:

Return exactly two columns: school_id, score
Return one row for every school in schools
Sort by school_id in ascending order

Supported submission environments:

SQL (SQLite 3.27.2)
Pandas (Python)

Example

Input

schools:
| school_id | capacity |
|-----------|----------|
| 11        | 151      |
| 5         | 48       |
| 9         | 9        |
| 10        | 99       |

exam:
| score | student_count |
|-------|---------------|
| 975   | 10            |
| 966   | 60            |
| 844   | 76            |
| 749   | 76            |
| 744   | 100           |

Output

[
  {"school_id":5,"score":975},
  {"school_id":9,"score":-1},
  {"school_id":10,"score":749},
  {"school_id":11,"score":744}
]

Explanation

School 10 can safely accept cutoffs 844 and 749 (both map to 76 applicants), so the tie-break picks the smaller score 749. School 9 has no safe cutoff and returns -1.

Example

Input

schools:
| school_id | capacity |
|-----------|----------|
| 1         | 2        |
| 2         | 3        |
| 3         | 8        |
| 4         | 1        |

exam:
| score | student_count |
|-------|---------------|
| 100   | 2             |
| 95    | 2             |
| 90    | 5             |
| 80    | 8             |
| 60    | 12            |

Output

[
  {"school_id":1,"score":95},
  {"school_id":2,"score":95},
  {"school_id":3,"score":80},
  {"school_id":4,"score":-1}
]

Explanation

For capacities 1 and 2, only student_count <= capacity is feasible. When multiple feasible scores share the same student_count (100 and 95), the smaller score 95 is chosen.

Example

Input

schools:
| school_id | capacity |
|-----------|----------|
| 21        | 0        |
| 22        | 100      |

exam:
| (no rows) |

Output

[
  {"school_id":21,"score":-1},
  {"school_id":22,"score":-1}
]

Explanation

Without exam score rows, no valid cutoff exists for any school, so every school returns -1.

Accepted0/0·0% Acceptance

Constraints

0 <= number of rows in schools <= 200000
0 <= number of rows in exam <= 200000
school_id is unique in schools
score is unique in exam
0 <= capacity <= 1000000000
0 <= student_count <= 1000000000
If score_a > score_b, then student_count_a <= student_count_b
Return exactly two columns: school_id, score
Return one row per school_id from schools
Sort output by school_id ascending
For SQL submissions, use SQLite 3.27.2 semantics
For Pandas submissions, return a DataFrame with columns school_id and score

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

exam =

[{"score":975,"student_count":10},{"score":966,"student_count":60},{"score":844,"student_count":76},{"score":749,"student_count":76},{"score":744,"student_count":100}]

schools =

[{"school_id":11,"capacity":151},{"school_id":5,"capacity":48},{"school_id":9,"capacity":9},{"school_id":10,"capacity":99}]

School Admission Cutoff Score Planner

Hints

School Admission Cutoff Score Planner

Hints