Q: Merge Intervals where intervals touching at an endpoint ([1,2] and [2,3]) count as overlapping. After sorting by start, when do you merge?

When start <= last end Touching counts as overlap, so start equal to the last end merges. Strict less keeps [1,2] and [2,3] apart. Comparing to last start ignores ends. end <= last end only handles containment.

Q: Merging [1,10] then [2,3]. Which update is right?

last[1] = max(last[1], cur[1]) Containment means the new end may be smaller, so take the max. Assigning cur[1] shrinks [1,10] to [1,3]. Replacing last loses the start. Appending ignores the overlap.

Q: Meeting Rooms: can one person attend all meetings, where a meeting ending at 10 and one starting at 10 do not conflict?

Sort by start and fail if any start < previous end Equal end and start is allowed, so only strict overlap fails. <= wrongly rejects back to back meetings. Comparing ends to ends misses overlaps. Every pair is O(n^2).

Q: Non-overlapping Intervals: minimum removals so the rest do not overlap. Which greedy is correct?

Sort by end, keep each interval that starts at or after the last kept end Keeping the earliest ending interval leaves the most room, the classic activity selection proof. Sorting by start keeps long early intervals that block many. Shortest first fails on cases where a short interval straddles two others. Max overlap removal is not proven optimal and is slow.

Q: Insert Interval into a sorted, non overlapping list. Best time?

O(n) One pass copies intervals before, merges the overlap and copies the rest. Re-sorting is unnecessary. Binary search finds the spot in O(log n) but the output still needs O(n). Repeated merging is not needed.

Q: Meeting Rooms II: minimum rooms to hold all meetings. Which is O(n log n)?

Sort by start, min heap of end times, pop while the top end <= current start The heap holds rooms in use, and its max size is the answer. Comparing only adjacent meetings misses three way overlaps. Same start counts ignore overlaps with different starts. Merging gives busy blocks, not concurrency.

Q: Sweep line for max concurrent meetings with events (time, +1) and (time, -1), half open intervals [start, end). How should ties sort?

End events (-1) before start events (+1) at the same time With half open intervals a meeting ending at t frees the room for one starting at t, so -1 first. Starts first overcounts back to back meetings. Ties change the max. Length is irrelevant.

Q: Jump Game: nums[i] is the max jump length from index i. Can you reach the last index? Which O(n) rule is correct?

Track the furthest reachable index and fail if i exceeds it The furthest reach invariant proves reachability. Max jumps can land on a 0 and miss a better shorter jump. DP is O(n^2), not O(n). Unmemoized recursion is exponential.

Question 1

Merge Intervals where intervals touching at an endpoint ([1,2] and [2,3]) count as overlapping. After sorting by start, when do you merge?

Accepted Answer

When start <= last end Touching counts as overlap, so start equal to the last end merges. Strict less keeps [1,2] and [2,3] apart. Comparing to last start ignores ends. end <= last end only handles containment.

Question 2

Merging [1,10] then [2,3]. Which update is right?

Accepted Answer

last[1] = max(last[1], cur[1]) Containment means the new end may be smaller, so take the max. Assigning cur[1] shrinks [1,10] to [1,3]. Replacing last loses the start. Appending ignores the overlap.

Question 3

Meeting Rooms: can one person attend all meetings, where a meeting ending at 10 and one starting at 10 do not conflict?

Accepted Answer

Sort by start and fail if any start < previous end Equal end and start is allowed, so only strict overlap fails. <= wrongly rejects back to back meetings. Comparing ends to ends misses overlaps. Every pair is O(n^2).

Question 4

Non-overlapping Intervals: minimum removals so the rest do not overlap. Which greedy is correct?

Accepted Answer

Sort by end, keep each interval that starts at or after the last kept end Keeping the earliest ending interval leaves the most room, the classic activity selection proof. Sorting by start keeps long early intervals that block many. Shortest first fails on cases where a short interval straddles two others. Max overlap removal is not proven optimal and is slow.

Question 5

Insert Interval into a sorted, non overlapping list. Best time?

Accepted Answer

O(n) One pass copies intervals before, merges the overlap and copies the rest. Re-sorting is unnecessary. Binary search finds the spot in O(log n) but the output still needs O(n). Repeated merging is not needed.

Question 6

Meeting Rooms II: minimum rooms to hold all meetings. Which is O(n log n)?

Accepted Answer

Sort by start, min heap of end times, pop while the top end <= current start The heap holds rooms in use, and its max size is the answer. Comparing only adjacent meetings misses three way overlaps. Same start counts ignore overlaps with different starts. Merging gives busy blocks, not concurrency.

Question 7

Sweep line for max concurrent meetings with events (time, +1) and (time, -1), half open intervals [start, end). How should ties sort?

Accepted Answer

End events (-1) before start events (+1) at the same time With half open intervals a meeting ending at t frees the room for one starting at t, so -1 first. Starts first overcounts back to back meetings. Ties change the max. Length is irrelevant.

Question 8

Jump Game: nums[i] is the max jump length from index i. Can you reach the last index? Which O(n) rule is correct?

Accepted Answer

Track the furthest reachable index and fail if i exceeds it The furthest reach invariant proves reachability. Max jumps can land on a 0 and miss a better shorter jump. DP is O(n^2), not O(n). Unmemoized recursion is exponential.

Question 9

Gas Station: on a circular route, station i gives gas[i] and driving to the next costs cost[i]. If total gas >= total cost, where do you start?

Accepted Answer

The index after the last point where the running tank went negative If you fail from s to j, no station between them can work, so restart after j; the total check guarantees that start succeeds. Index 0 can fail. Most gas or best single gain ignores the route.

Question 10

You claim that picking the interval with the earliest end is optimal for maximum non overlapping intervals. The interviewer asks you to prove it. Which argument is a valid proof?

Accepted Answer

Show any optimal solution can be changed to include the greedy choice without getting worse Exchange arguments transform an optimal solution step by step into the greedy one. Random tests are not proof. Local optimality alone is the claim, not the proof. Runtime says nothing about correctness.

Question 11

Partition Labels (split a string into as many parts as possible so each letter appears in one part only): what drives the cut points?

Accepted Answer

The last index of each character; cut when i equals the max last index seen Extend the current part to the furthest last occurrence of any letter in it, and cut when you reach it. First indexes do not bound a part. Frequencies ignore position. Cutting on repeats splits letters across parts.

Intervals and greedy coding interview questions

Intervals

Greedy

More coding topics

Practise these on your commute