ORIGINAL CODING QUESTION

Most non-overlapping sessions

Select as many sessions as possible with no overlap. Sessions are half-open [start,end), so touching endpoints are compatible.

Open practice workspace

Original exercise · medium. Editorial role relevance does not imply a company has asked this question.

Input and output

n, then n start/end pairs.

Constraints

1 ≤ n ≤ 200; 0 ≤ start < end ≤ 10000.

Example 1

Input

3 0 2 1 3 2 4

Output

Sessions [0,2) and [2,4) are compatible.

Example 2

Input

3 0 5 1 4 2 3

Output

Only one can be selected.

Explain your approach

Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?

Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.

Hint 1

A session ending earlier leaves more room afterward.

Hint 2

Sort by end time.

Hint 3

Accept each next session whose start is at least the prior selected end.

Practice this question

Save your work privately, explain decisions and return to your revision queue.

Open practice workspace Browse the question library →