Pinterest·Data Scientist·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Pinterest data scientist interview with a scheduling algorithm problem. Pretty standard greedy interval question but I blanked on the approach for longer than I'd like to admit.

Questions Asked (1)

You have a list of tasks with start and end times on a single machine. How do you find the maximum number of tasks you can run without any overlap? For example, given [[1,3],[1,5],[4,6]], the answer is 2.

Algorithms & Data Structures

Author's notes

Spent the first couple minutes thinking about it wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize this as the classic interval scheduling maximization problem and propose a greedy solution: sort tasks by end time, then iterate through tasks, selecting each task that starts at or after the end of the last selected task. This yields the maximum number of non-overlapping tasks in O(n log n) time.

Pro tip: Mention that this greedy strategy is provably optimal and briefly explain the exchange argument: any optimal solution can be transformed to include the earliest-finishing task without reducing the count. This shows depth beyond just coding the solution.

1. Clarify the problem

Confirm that tasks cannot overlap and that each task runs on a single machine, so we need the maximum subset of non-overlapping intervals. Ask if intervals are inclusive/exclusive or if zero-length tasks are allowed.

2. Identify the algorithmic pattern

Recognize this as the interval scheduling maximization problem, which is solvable with a greedy approach. Contrast with other interval problems (e.g., merging intervals) to show you understand the distinction.

3. Describe the greedy strategy

Sort tasks by end time ascending. Initialize last_end = -infinity and count = 0. For each task in sorted order, if task.start >= last_end, select it, update last_end = task.end, and increment count.

4. Analyze complexity and prove optimality

State that sorting takes O(n log n) and the single pass takes O(n), so overall O(n log n) time and O(1) extra space (if sorting in place). Explain why greedy works: the earliest finishing task leaves the most room for subsequent tasks.

5. Walk through the example

Apply the algorithm to [[1,3],[1,5],[4,6]]: sort by end time -> [[1,3],[1,5],[4,6]]. Select [1,3] (last_end=3). Next [1,5] starts at 1 < 3, skip. Next [4,6] starts at 4 >= 3, select (last_end=6). Count=2.

Key Points to Mention

Greedy algorithm: sort by end time and pick earliest finishing compatible task
Time complexity: O(n log n) due to sorting, O(n) for the scan
Space complexity: O(1) extra space if sorting in place, otherwise O(n) for sorted copy
Proof of optimality via exchange argument: replacing the first task in an optimal solution with the earliest finishing task does not reduce the number of tasks
Edge cases: empty list, tasks with same start/end, tasks that are back-to-back (end == start of next)
Contrast with dynamic programming approach for weighted interval scheduling (where greedy fails)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.