School Admission Cutoff Score Planner

Medium

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 1

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 2

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 3

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.

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

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 |

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 |