What Is a Half-Open Interval? Why Touching Meetings Do Not Overlap
A half-open interval includes the start and excludes the end. Two meetings that touch at that endpoint do not overlap, which is the rule interval scheduling relies on.
A half-open interval [start, end) contains every time from the start up to, but not including, the end. A meeting that ends at 3 and a meeting that starts at 3 do not overlap. One person can attend both.
How it works
Two intervals overlap when one starts before the other has finished. In numbers, after you sort by start, they overlap when the next start is strictly less than the previous end. Equal starts and ends touch, and touching is allowed.
Interval scheduling sorts by finishing time and repeatedly takes the interval that frees you soonest. The half-open rule is why [1, 3] and [3, 5] can both be kept. Sorting by start time instead lets a long early interval block several short ones. That is a rule you can break with one example, so it is not the rule.
Press Run to execute this example. Use console.log to print a value.
Expected output: [[1, 3], [3, 5]]. The first two intervals touch at 3 but do not overlap; choosing [2, 6) would finish later and leave less room.
Worked example
Sorting by finish gives [1, 3), [3, 5), then [2, 6). Choose the first and set availableFrom to 3. The second starts at 3, so it is compatible and moves the boundary to 5. The last starts at 2, before 5, so skip it.
Why it is correct
Consider an optimal schedule's first interval. The greedy interval finishes no later because it has the earliest finish overall. Replacing the optimal first interval with the greedy one cannot make any later interval unavailable. The remaining problem is the same scheduling problem after that finish time, so repeating this exchange argument proves that every greedy choice can belong to an optimal schedule.
Cost
Sorting n intervals takes O(n log n) time; the selection scan takes O(n). The copied ordering and chosen result use O(n) space, while the caller's input remains unchanged. If intervals were already sorted by finish time, selection alone would be linear.
In the course
Greedy algorithms use half-open intervals for the largest set you can keep, and for whether one person can attend every meeting. The next lesson asks for the single interval that finishes first, with a tie broken by the smaller start.
Common mistakes
Treating a shared endpoint as an overlap. The tests allow touching.
Sorting by start and assuming the count is optimal. A long early interval is the counterexample.
Comparing ends with <= when the intervals are half-open. nextStart < previousEnd is the overlap test. <= rejects a meeting that starts when the previous one ends.
When to use it
Use half-open intervals for time ranges and for array slices, where the end index is the first position not included. The same convention shows up in slice(start, end).
When not to
Do not use a half-open overlap test on closed intervals that include both ends. A shared endpoint then really is a conflict, and the comparison changes.
Problem-solving checklist
Write the interval convention before choosing a comparison. Build a counterexample for each proposed greedy sorting rule. Test touching intervals, nested intervals, equal finishes, and an empty list. Preserve the input if mutation is not part of the contract.
Optional enrichment
Write separate overlap predicates for half-open and closed intervals. Use the same endpoint-touching example to show why the two predicates must disagree.