Clashing Exam Slots in Students' Timetables — SQL Problem
Before publishing the end-semester timetable, the exam cell checks every student's registered exams for clashes: two exams whose time slots overlap.
- Difficulty: Hard
- Topics: Joins, Dates
- Dialect: MySQL
- Problem: #146
Problem statement
Before publishing the end-semester timetable, the exam cell checks every student's registered exams for clashes: two exams whose time slots overlap. An exam ending at the very minute another begins is not a clash.
Return one row per clashing pair per student with the columns roll_no, first_subject, second_subject and overlap_minutes (how long the two slots overlap). In each pair the first_subject is the exam that starts earlier; for two exams starting together, the one with the smaller exam_id. Order the rows by roll_no, then by first_subject, then by second_subject.
Tables
Table: ExamSlot
| Column | Type |
|---|---|
| exam_id | int |
| subject_code | varchar |
| starts_at | datetime |
| ends_at | datetime |
Primary key: exam_id.
One slot per subject (subject_code is unique); ends_at is always after starts_at.
Table: ExamRegistration
| Column | Type |
|---|---|
| roll_no | int |
| exam_id | int |
Primary key: roll_no, exam_id.
The exams each student must sit, regular and backlog papers alike.
Examples
Example 1
ExamSlot
| exam_id | subject_code | starts_at | ends_at |
|---|---|---|---|
| 1 | CS301 | 2024-11-18 09:30:00 | 2024-11-18 12:30:00 |
| 2 | MA201 | 2024-11-18 11:00:00 | 2024-11-18 13:00:00 |
| 3 | HS101 | 2024-11-18 12:30:00 | 2024-11-18 14:00:00 |
| 4 | EC210 | 2024-11-19 09:30:00 | 2024-11-19 12:30:00 |
| 5 | ME105 | 2024-11-19 09:30:00 | 2024-11-19 11:00:00 |
ExamRegistration
| roll_no | exam_id |
|---|---|
| 2101 | 1 |
| 2101 | 2 |
| 2101 | 3 |
| 2102 | 1 |
| 2102 | 3 |
| 2103 | 4 |
| 2103 | 5 |
| 2103 | 2 |
Output
| roll_no | first_subject | second_subject | overlap_minutes |
|---|---|---|---|
| 2101 | CS301 | MA201 | 90 |
| 2101 | MA201 | HS101 | 30 |
| 2103 | EC210 | ME105 | 90 |
How to solve Clashing Exam Slots in Students' Timetables
Clashes are pairs of rows, so the shape is a self join: each registration is joined with the same student's other registrations, and both sides are joined to ExamSlot for their times.
Two intervals [s1, e1) and [s2, e2) overlap exactly when s1 < e2 AND s2 < e1. The comparisons are strict, so slots that merely touch — 09:30–12:30 and 12:30–14:00 — are not a clash. This single test covers every arrangement: one slot inside the other, partial overlaps on either side, identical slots.
A self join produces every clash twice, as (A, B) and (B, A). The orientation rule in the statement picks one: the first exam starts earlier, or starts at the same time with the smaller exam_id. The overlap is from the later of the two starts to the earlier of the two ends, TIMESTAMPDIFF(MINUTE, GREATEST(starts), LEAST(ends)).
The alternative computes that duration for every oriented pair and keeps the positive ones, which is the same condition expressed through the result. The cost is quadratic in each student's registrations, which is a handful.
Reference solution (MySQL)
SELECT ra.roll_no, a.subject_code AS first_subject, b.subject_code AS second_subject,
TIMESTAMPDIFF(MINUTE, GREATEST(a.starts_at, b.starts_at), LEAST(a.ends_at, b.ends_at)) AS overlap_minutes
FROM ExamRegistration ra
JOIN ExamRegistration rb ON rb.roll_no = ra.roll_no AND rb.exam_id <> ra.exam_id
JOIN ExamSlot a ON a.exam_id = ra.exam_id
JOIN ExamSlot b ON b.exam_id = rb.exam_id
WHERE a.starts_at < b.ends_at AND b.starts_at < a.ends_at
AND (a.starts_at < b.starts_at OR (a.starts_at = b.starts_at AND a.exam_id < b.exam_id))
ORDER BY ra.roll_no, first_subject, second_subjectAnother way
SELECT roll_no, first_subject, second_subject, overlap_minutes FROM (SELECT ra.roll_no, a.subject_code AS first_subject, b.subject_code AS second_subject, TIMESTAMPDIFF(MINUTE, CASE WHEN a.starts_at > b.starts_at THEN a.starts_at ELSE b.starts_at END, CASE WHEN a.ends_at < b.ends_at THEN a.ends_at ELSE b.ends_at END) AS overlap_minutes FROM ExamRegistration ra, ExamRegistration rb, ExamSlot a, ExamSlot b WHERE ra.roll_no = rb.roll_no AND a.exam_id = ra.exam_id AND b.exam_id = rb.exam_id AND (a.starts_at < b.starts_at OR (a.starts_at = b.starts_at AND a.exam_id < b.exam_id))) t WHERE overlap_minutes > 0 ORDER BY 1, 2, 3← Top Three Scores in Each National Mock Test · Day Each Branch Crossed 50% Placement →