DSA-038 · FOCUSED PRACTICE

Meeting Rooms — Conflict Detection

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 9342 deterministic checks. Learner drafts are not executed.

Understand the problem

Determine whether one person can attend every positive-duration meeting without a time conflict.

meetings is a non-null int[][] with 0–100,000 rows [start,end] of signed int times. Both methods throw IllegalArgumentException for null/malformed rows or start≥end. Zero-duration meetings are rejected rather than silently ignored.
Meetings occupy half-open [start,end). End at t and start at t are compatible; equal starts for two positive-duration meetings conflict. Empty and singleton valid inputs return true.
Return a boolean and preserve source outer order and row values. Sort a cloned outer array by start, reading rows without modification. No duration arithmetic or time-zone interpretation is involved; coordinates are ordered integer instants.

Examples

Input: [[0,30],[5,10],[15,20]]
Output: false
The first long meeting conflicts with the meeting starting at five.
Input: [[7,10],[2,4],[4,7]]
Output: true
Sorting gives a compatible chain; equal end/start boundaries do not overlap.

Before you start

Closed versus half-open intervals and compatible endpoints
Sorting with safe comparators and invariant or exchange proofs

Recognize the structure

This is a feasibility question about keeping every meeting. Sorting by start makes the first adjacent overlap sufficient to reject feasibility, and a conflict-free prefix makes checking the next adjacent pair sufficient to extend it.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 145/20,000 characters

Self-review

I can prove adjacency suffices after sorting.I allow end/start equality.I distinguish feasibility from removal and room-count objectives.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

After sorting by start, where must the first conflict appear?

Hint 2

What does a conflict-free prefix tell you about all its earlier end times?

Hint 3

Reject an adjacent strict overlap; otherwise extend the compatible chain.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Check every unordered pair

For each i<j, compare max(start[i],start[j]) with min(end[i],end[j]); a strict smaller start intersection means positive overlap. On [1,3) and [3,5), max starts equals min ends, so they are compatible. On [1,4) and [3,5), 3<4 proves a conflict. This O(n²) baseline needs constant other state.

Improve the baseline

Order meetings by start

Clone the outer array and sort with a safe start comparator. The input need not arrive in chronological order.

Compare each adjacent pair

For sorted current meeting i, reject if start[i]<end[i-1]. Equality is allowed because the earlier meeting releases its endpoint.

Extend a conflict-free prefix

If every tested adjacent pair is compatible, every earlier meeting ends no later than the next start in the chain, so the whole set is attendable.

Why it is correct

Sound conflict witness

If start[i]<end[i-1], sorted order gives start[i-1]≤start[i], and positive durations ensure the later meeting continues beyond its own start. The two adjacent intervals therefore share occupied time.

Conflict-free prefix induction

Initially one meeting is feasible. If the first i meetings are pairwise compatible in start order, their end/start chain is ordered. end[i-1]≤start[i] puts the new meeting after every earlier one, preserving global feasibility.

Completion and scope

Returning true after all adjacent checks proves all meetings fit, not just nearby ones. Returning false needs only one sound witness. Empty input has no pairs and is feasible; validation handles malformed or zero-duration rows first.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(int[][] meetings) {
        for (int[] row : meetings) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open meetings required");
    }
    public static boolean canAttendMeetings(int[][] meetings) {
        validate(meetings);
        int[][] sorted = meetings.clone();
        Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
        for (int i = 1; i < sorted.length; i++) if (sorted[i][0] < sorted[i - 1][1]) return false;
        return true;
    }
    public static boolean baseline(int[][] meetings) {
        validate(meetings);
        for (int i = 0; i < meetings.length; i++) for (int j = i + 1; j < meetings.length; j++)
            if (Math.max(meetings[i][0], meetings[j][0]) < Math.min(meetings[i][1], meetings[j][1])) return false;
        return true;
    }
}

Read the meaningful blocks

Strict overlap comparison

startCurrent<endPrevious rejects positive overlap; changing it to ≤ would reject legal back-to-back meetings.

Adjacent end is sufficient here

The algorithm returns immediately at the first conflict. It is not trying to continue a conflictful prefix using only the most recent end.

Sort a copy of references

No row values are changed, so cloning the outer order is enough to preserve the input for a scalar query.

Complexity

O(n log n) time and O(n) auxiliary space for the outer clone and object-sort workspace. The scan itself uses O(1) state and may stop at the first conflict.

The pairwise baseline costs O(n²) time and O(1) other workspace. If input is already guaranteed sorted, a separate streaming API can check adjacent meetings in O(n) time and O(1) state.

Exact-state walkthroughs

Reveal normal and boundary traces

An unsorted compatible chain

Input: [[7,10],[2,4],[4,7]] · Result: true

Step 1 of 4: Sort a copied order by start and initialize a feasible prefix.

Zero or one validated positive-duration meeting is trivially conflict-free.

Half-open meeting coordinates — end excluded

Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions.

Row #0: [2, 4)
Row #1: [4, 7)
Row #2: [7, 10)

State after this step
Variable	Value
intervalRows	`[[2,4],[4,7],[7,10]]`
index	`-1`
checkedThrough	`0`
closed	`false`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int[][] meetings) {
 4         for (int[] row : meetings) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open meetings required");
 5     }
 6     public static boolean canAttendMeetings(int[][] meetings) {
 7         validate(meetings);
 8         int[][] sorted = meetings.clone();
 9         Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
10         for (int i = 1; i < sorted.length; i++) if (sorted[i][0] < sorted[i - 1][1]) return false;
11         return true;
12     }
13     public static boolean baseline(int[][] meetings) {
14         validate(meetings);
15         for (int i = 0; i < meetings.length; i++) for (int j = i + 1; j < meetings.length; j++)
16             if (Math.max(meetings[i][0], meetings[j][0]) < Math.min(meetings[i][1], meetings[j][1])) return false;
17         return true;
18     }
19 }
20

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a copied order by start and initialize a feasible prefix.
Zero or one validated positive-duration meeting is trivially conflict-free.
intervalRows
[[2,4],[4,7],[7,10]]
index
-1
checkedThrough
0
closed
false
Extend the conflict-free start-ordered chain.
The previous end is at most this start, so every earlier meeting also finishes in time.
intervalRows
[[2,4],[4,7],[7,10]]
index
1
previousEnd
4
currentStart
4
conflict
false
checkedThrough
1
closed
false
Extend the conflict-free start-ordered chain.
The previous end is at most this start, so every earlier meeting also finishes in time.
intervalRows
[[2,4],[4,7],[7,10]]
index
2
previousEnd
7
currentStart
7
conflict
false
checkedThrough
2
closed
false
Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
result
true

Containment gives an immediate conflict

Input: [[0,100],[1,2],[3,4]] · Result: false

Step 1 of 3: Sort a copied order by start and initialize a feasible prefix.

Zero or one validated positive-duration meeting is trivially conflict-free.

Half-open meeting coordinates — end excluded

Row #0: [0, 100)
Row #1: [1, 2)
Row #2: [3, 4)

State after this step
Variable	Value
intervalRows	`[[0,100],[1,2],[3,4]]`
index	`-1`
checkedThrough	`0`
closed	`false`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int[][] meetings) {
 4         for (int[] row : meetings) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open meetings required");
 5     }
 6     public static boolean canAttendMeetings(int[][] meetings) {
 7         validate(meetings);
 8         int[][] sorted = meetings.clone();
 9         Arrays.sort(sorted, Comparator.comparingInt(value -> value[0]));
10         for (int i = 1; i < sorted.length; i++) if (sorted[i][0] < sorted[i - 1][1]) return false;
11         return true;
12     }
13     public static boolean baseline(int[][] meetings) {
14         validate(meetings);
15         for (int i = 0; i < meetings.length; i++) for (int j = i + 1; j < meetings.length; j++)
16             if (Math.max(meetings[i][0], meetings[j][0]) < Math.min(meetings[i][1], meetings[j][1])) return false;
17         return true;
18     }
19 }
20

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a copied order by start and initialize a feasible prefix.
Zero or one validated positive-duration meeting is trivially conflict-free.
intervalRows
[[0,100],[1,2],[3,4]]
index
-1
checkedThrough
0
closed
false
Reject a sound adjacent conflict witness.
The two adjacent positive-duration intervals overlap.
intervalRows
[[0,100],[1,2],[3,4]]
index
1
previousEnd
100
currentStart
1
conflict
true
checkedThrough
0
closed
false
Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
result
false

Test the contract

Input: []
Output: true
No conflicts.
Input: [[1,5]]
Output: true
One valid meeting.
Input: [[1,3],[1,2]]
Output: false
Equal starts overlap for positive durations.
Input: [[2,2]]
Output: IllegalArgumentException
Zero-duration policy is explicit.

Common mistakes and counterexamples

Reject equality

Counterexample: [1,2) followed by [2,3) is attendable.

Use strict start<previousEnd for conflict.

Sort the caller array in place

Counterexample: The boolean result does not authorize reordering caller data.

Sort meetings.clone() and keep rows read-only.

Skip a conflict because a later short interval ends early

Counterexample: [0,100),[1,2),[3,4) already conflicts at the first pair.

Return at the first sound adjacent witness; do not reset feasibility afterward.

Follow-ups

Return a conflict witness.

Sort value/index records and return the two original meeting identities at the first conflict. Define whether any witness or the earliest chronological witness is required.

Check a sorted stream.

Keep only the previous end after validating each positive-duration record. The sorted-order precondition replaces in-memory sorting; reject an out-of-order stream if the API promises validation.

Count required rooms.

A boolean only distinguishes peak concurrency at most one from greater than one. To find the full resource requirement, track all active end times or sweep start/end events, as in the next lesson.

Related foundations

Intervals: define endpoints and the requested operation

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.