Kth Largest Element in Array

🎯

Kth Largest Element in Array

mediumHEAPFacebookAmazonGoogle

Imagine you are analyzing sales data and want to find the product with the kth highest sales quickly without sorting the entire dataset.

💡 This problem is about finding a specific order statistic (the kth largest element) in an unsorted array. Beginners often struggle because sorting the entire array is straightforward but inefficient, and more optimal methods require understanding heaps or partitioning algorithms.

📋

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^91 ≤ k ≤ nums.length

💡

Example

Input"nums = [3,2,1,5,6,4], k = 2"

Output5

The sorted array is [1,2,3,4,5,6]. The 2nd largest element is 5.

• k = 1 (largest element) → returns max element
• k = length of array (smallest element) → returns min element
• all elements equal → returns that element
• array with negative and positive numbers → handles sign correctly

⚠️

Common Mistakes

Using sort() without specifying numeric comparator in JavaScript

Incorrect sorting order leading to wrong kth largest element

✅ Use nums.sort((a,b) => a - b) for numeric ascending sort

Off-by-one errors in indexing kth largest element

Returns wrong element, often kth smallest instead

✅ Remember kth largest is at index length - k after sorting or adjust partition accordingly

Not maintaining heap size k in min heap approach

Heap grows too large, increasing time and space complexity

✅ Always remove smallest element when heap size exceeds k

Choosing poor pivot in quickselect leading to worst-case O(n^2)

Algorithm slows down significantly on certain inputs

✅ Use random pivot or median-of-three to improve average performance

Modifying input array without copying when not allowed

Unexpected side effects or interview feedback

✅ Clarify if input can be modified or work on a copy

🧠

Brute Force (Sort Entire Array)

💡 Sorting the entire array is the most straightforward way to find the kth largest element. It helps beginners understand the problem fully before optimizing.

Intuition

If we sort the array in ascending order, the kth largest element is at index length-k. This approach leverages built-in sorting to simplify the problem.

Algorithm

1. Sort the array in ascending order.
2. Return the element at index length - k.

💡 This algorithm is simple but inefficient for large arrays because it sorts everything even though we only need one element.

</>

Code

def findKthLargest(nums, k):
    nums.sort()
    return nums[-k]

# Driver code
if __name__ == '__main__':
    print(findKthLargest([3,2,1,5,6,4], 2))  # Output: 5

Line Notes

def findKthLargest(nums, k):Defines the function signature for clarity and reuse

nums.sort()Sorts the entire array in ascending order to arrange elements

return nums[-k]Returns the kth largest element by indexing from the end

print(findKthLargest([3,2,1,5,6,4], 2))Tests the function with a sample input to verify correctness

import java.util.*;
public class Solution {
    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println(findKthLargest(nums, 2)); // Output: 5
    }
}

Line Notes

public static int findKthLargest(int[] nums, int k)Defines the method signature for clarity and reuse

Arrays.sort(nums);Sorts the array in ascending order using built-in method

return nums[nums.length - k];Returns the kth largest element by indexing from the end

System.out.println(findKthLargest(nums, 2));Tests the method with sample input to verify correctness

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() - k];
}

int main() {
    vector<int> nums = {3,2,1,5,6,4};
    cout << findKthLargest(nums, 2) << endl; // Output: 5
    return 0;
}

Line Notes

int findKthLargest(vector<int>& nums, int k)Function signature for clarity and reuse

sort(nums.begin(), nums.end());Sorts the vector in ascending order using STL sort

return nums[nums.size() - k];Returns the kth largest element by indexing from the end

cout << findKthLargest(nums, 2) << endl;Prints the result for verification

function findKthLargest(nums, k) {
    nums.sort((a, b) => a - b);
    return nums[nums.length - k];
}

// Test
console.log(findKthLargest([3,2,1,5,6,4], 2)); // Output: 5

Line Notes

function findKthLargest(nums, k)Defines the function for clarity and reuse

nums.sort((a, b) => a - b);Sorts the array numerically in ascending order

return nums[nums.length - k];Returns the kth largest element by indexing from the end

console.log(findKthLargest([3,2,1,5,6,4], 2));Logs the output to verify correctness

⏱

Complexity

TimeO(n log n)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n) time; accessing the kth element is O(1).

💡 For n=100,000, sorting means roughly 1.5 million operations, which is slow but acceptable for medium input sizes.

Interview Verdict: Accepted but not optimal

This approach works but is inefficient for large inputs; interviewers expect better solutions.

🧠

Min Heap of Size k

💡 Using a min heap of size k helps maintain the top k largest elements efficiently without sorting the entire array.

Intuition

Keep a min heap with the k largest elements seen so far. The heap root is the smallest among them, so after processing all elements, the root is the kth largest.

Algorithm

1. Create a min heap and add the first k elements.
2. For each remaining element, if it is larger than the heap root, replace the root with this element and heapify.
3. After processing all elements, the root of the heap is the kth largest element.

💡 This algorithm avoids sorting the entire array and only keeps track of k elements, making it more efficient for large arrays.

</>

Code

import heapq

def findKthLargest(nums, k):
    min_heap = nums[:k]
    heapq.heapify(min_heap)
    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    return min_heap[0]

# Driver code
if __name__ == '__main__':
    print(findKthLargest([3,2,1,5,6,4], 2))  # Output: 5

Line Notes

import heapqImports heapq module to use heap operations

min_heap = nums[:k]Initialize heap with first k elements to track top k

heapq.heapify(min_heap)Transforms list into a min heap in O(k) time

if num > min_heap[0]Check if current number is bigger than smallest in heap

heapq.heapreplace(min_heap, num)Replace smallest with current number and reheapify

return min_heap[0]The root of the min heap is the kth largest element

import java.util.*;
public class Solution {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }
    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println(findKthLargest(nums, 2)); // Output: 5
    }
}

Line Notes

import java.util.*;Imports utility classes including PriorityQueue

PriorityQueue<Integer> minHeap = new PriorityQueue<>();Creates a min heap to store k largest elements

minHeap.offer(nums[i]);Adds elements to the heap

if (nums[i] > minHeap.peek())Checks if current element is larger than smallest in heap

minHeap.poll(); minHeap.offer(nums[i]);Removes smallest and adds current element to maintain size k

return minHeap.peek();Returns the kth largest element at the root of the min heap

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int i = 0; i < k; i++) {
        minHeap.push(nums[i]);
    }
    for (int i = k; i < nums.size(); i++) {
        if (nums[i] > minHeap.top()) {
            minHeap.pop();
            minHeap.push(nums[i]);
        }
    }
    return minHeap.top();
}

int main() {
    vector<int> nums = {3,2,1,5,6,4};
    cout << findKthLargest(nums, 2) << endl; // Output: 5
    return 0;
}

Line Notes

#include <queue>Includes priority_queue for heap operations

priority_queue<int, vector<int>, greater<int>> minHeap;Defines a min heap using greater comparator

minHeap.push(nums[i]);Adds elements to the min heap

if (nums[i] > minHeap.top())Checks if current element is bigger than smallest in heap

minHeap.pop(); minHeap.push(nums[i]);Replaces smallest element to maintain top k

return minHeap.top();Returns the kth largest element at the root of the min heap

class MinHeap {
    constructor() {
        this.heap = [];
    }
    parent(i) { return Math.floor((i - 1) / 2); }
    left(i) { return 2 * i + 1; }
    right(i) { return 2 * i + 2; }
    swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }
    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }
    bubbleUp(i) {
        while (i > 0 && this.heap[this.parent(i)] > this.heap[i]) {
            this.swap(i, this.parent(i));
            i = this.parent(i);
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return top;
    }
    bubbleDown(i) {
        let smallest = i;
        const left = this.left(i);
        const right = this.right(i);
        if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
        if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
        if (smallest !== i) {
            this.swap(i, smallest);
            this.bubbleDown(smallest);
        }
    }
    top() {
        return this.heap[0];
    }
    size() {
        return this.heap.length;
    }
}

function findKthLargest(nums, k) {
    const minHeap = new MinHeap();
    for (let i = 0; i < k; i++) {
        minHeap.push(nums[i]);
    }
    for (let i = k; i < nums.length; i++) {
        if (nums[i] > minHeap.top()) {
            minHeap.pop();
            minHeap.push(nums[i]);
        }
    }
    return minHeap.top();
}

// Test
console.log(findKthLargest([3,2,1,5,6,4], 2)); // Output: 5

Line Notes

class MinHeap {Defines a custom min heap class to manage heap operations

this.heap.push(val);Adds new element at the end before bubbling up

this.bubbleUp(this.heap.length - 1);Restores heap property after insertion

if (nums[i] > minHeap.top())Checks if current element should replace smallest in heap

minHeap.pop(); minHeap.push(nums[i]);Replaces smallest element to maintain top k

return minHeap.top();Returns the kth largest element at the root of the min heap

⏱

Complexity

TimeO(n log k)

SpaceO(k)

Building and maintaining a heap of size k takes O(log k) per insertion, done n times.

💡 For n=100,000 and k=10, this means about 100,000 * log(10) ≈ 300,000 operations, much faster than sorting.

Interview Verdict: Accepted and efficient for large n with small k

This approach is a common interview favorite because it balances simplicity and efficiency.

🧠

Quickselect (Partition-based Selection)

💡 Quickselect is an efficient selection algorithm related to quicksort that finds the kth largest element without sorting the entire array.

Intuition

Partition the array around a pivot so that elements greater than pivot are on one side. Recursively search the side that contains the kth largest element until found.

Algorithm

1. Choose a pivot element randomly or from the array.
2. Partition the array so elements greater than pivot are on the left, smaller on the right.
3. Check the pivot's position; if it matches kth largest index, return it.
4. Otherwise, recurse on the side that contains the kth largest element.

💡 This algorithm is tricky because it uses partitioning logic and recursion, but it avoids sorting the entire array.

</>

Code

import random

def partition(nums, left, right):
    pivot = nums[right]
    i = left
    for j in range(left, right):
        if nums[j] > pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[right] = nums[right], nums[i]
    return i

def quickselect(nums, left, right, k):
    if left == right:
        return nums[left]
    pivot_index = partition(nums, left, right)
    if pivot_index == k:
        return nums[pivot_index]
    elif pivot_index < k:
        return quickselect(nums, pivot_index + 1, right, k)
    else:
        return quickselect(nums, left, pivot_index - 1, k)

def findKthLargest(nums, k):
    return quickselect(nums, 0, len(nums) - 1, k - 1)

# Driver code
if __name__ == '__main__':
    print(findKthLargest([3,2,1,5,6,4], 2))  # Output: 5

Line Notes

import randomImports random module if pivot randomization is added (currently unused)

def partition(nums, left, right):Partitions array around pivot for quickselect

pivot = nums[right]Selects the last element as pivot for partitioning

if nums[j] > pivot:Ensures elements greater than pivot go to left side

nums[i], nums[j] = nums[j], nums[i]Swaps elements to maintain partition invariant

if pivot_index == k:Checks if pivot is at kth largest position to return result

import java.util.*;
public class Solution {
    public static int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] > pivot) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }
        int temp = nums[i];
        nums[i] = nums[right];
        nums[right] = temp;
        return i;
    }
    public static int quickselect(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == k) return nums[pivotIndex];
        else if (pivotIndex < k) return quickselect(nums, pivotIndex + 1, right, k);
        else return quickselect(nums, left, pivotIndex - 1, k);
    }
    public static int findKthLargest(int[] nums, int k) {
        return quickselect(nums, 0, nums.length - 1, k - 1);
    }
    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println(findKthLargest(nums, 2)); // Output: 5
    }
}

Line Notes

import java.util.*;Imports utility classes

int pivot = nums[right];Chooses pivot as last element for partitioning

if (nums[j] > pivot)Partitions elements greater than pivot to left

int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;Swaps elements to maintain partition

if (pivotIndex == k)Checks if pivot is kth largest element

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] > pivot) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[right]);
    return i;
}

int quickselect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];
    int pivotIndex = partition(nums, left, right);
    if (pivotIndex == k) return nums[pivotIndex];
    else if (pivotIndex < k) return quickselect(nums, pivotIndex + 1, right, k);
    else return quickselect(nums, left, pivotIndex - 1, k);
}

int findKthLargest(vector<int>& nums, int k) {
    return quickselect(nums, 0, nums.size() - 1, k - 1);
}

int main() {
    vector<int> nums = {3,2,1,5,6,4};
    cout << findKthLargest(nums, 2) << endl; // Output: 5
    return 0;
}

Line Notes

#include <vector>Includes vector container

int pivot = nums[right];Selects pivot element for partitioning

if (nums[j] > pivot)Partitions elements greater than pivot to left

swap(nums[i], nums[j]);Swaps elements to maintain partition invariant

if (pivotIndex == k)Checks if pivot is at kth largest position

function partition(nums, left, right) {
    let pivot = nums[right];
    let i = left;
    for (let j = left; j < right; j++) {
        if (nums[j] > pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }
    [nums[i], nums[right]] = [nums[right], nums[i]];
    return i;
}

function quickselect(nums, left, right, k) {
    if (left === right) return nums[left];
    let pivotIndex = partition(nums, left, right);
    if (pivotIndex === k) return nums[pivotIndex];
    else if (pivotIndex < k) return quickselect(nums, pivotIndex + 1, right, k);
    else return quickselect(nums, left, pivotIndex - 1, k);
}

function findKthLargest(nums, k) {
    return quickselect(nums, 0, nums.length - 1, k - 1);
}

// Test
console.log(findKthLargest([3,2,1,5,6,4], 2)); // Output: 5

Line Notes

function partition(nums, left, right)Partitions array around pivot for quickselect

let pivot = nums[right];Selects pivot element for partitioning

if (nums[j] > pivot)Partitions elements greater than pivot to left

[nums[i], nums[j]] = [nums[j], nums[i]];Swaps elements to maintain partition

if (pivotIndex === k)Checks if pivot is kth largest element

⏱

Complexity

TimeAverage O(n), Worst O(n^2)

SpaceO(1) additional space

Partitioning reduces problem size each recursion; average case is linear but worst case is quadratic.

💡 For n=100,000, average case is about 100,000 operations, but worst case can degrade if pivot choices are poor.

Interview Verdict: Accepted and optimal average case

Quickselect is the fastest average solution but requires careful implementation and understanding of partitioning.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the min heap or quickselect approach is preferred due to efficiency and clarity. Sorting is acceptable for small inputs or as a baseline.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Sort Entire Array)	O(n log n)	O(1) or O(n)	No	N/A	Mention only - never code unless asked for baseline
2. Min Heap of Size k	O(n log k)	O(k)	No	N/A	Good balance of efficiency and simplicity; code if comfortable
3. Quickselect (Partition-based Selection)	Average O(n), Worst O(n^2)	O(1)	Yes (deep recursion)	N/A	Optimal but requires careful implementation; code if confident

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then discuss more efficient methods. Practice coding and explaining each approach clearly.

How to Present

Clarify the problem and constraints with the interviewer.State the brute force approach using sorting and its complexity.Discuss the min heap approach and why it improves efficiency.Explain quickselect as the optimal average-case solution.Choose one approach to implement based on time and interviewer hints.Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Testing & optimization: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize, coding skills, and handling of edge cases.

Common Follow-ups

• What if the array is sorted? → You can return directly or optimize.
• How to find kth smallest instead? → Adjust indexing or partition logic.

💡 These follow-ups test your adaptability and understanding of order statistics variations.

🔍

Pattern Recognition

When to Use

1) Need kth largest or smallest element; 2) Input is unsorted; 3) Want better than full sort; 4) Can use heap or partitioning

Signature Phrases

'kth largest element''find kth order statistic''without sorting entire array'

NOT This Pattern When

Sorting entire array without optimization or problems requiring all elements sorted

Similar Problems

Top K Frequent Elements - uses heaps to find most frequent itemsKth Smallest Element in a Sorted Matrix - uses heap or binary search for orderFind Median from Data Stream - uses two heaps to maintain median

Practice

1. Consider the following Python code implementing a frequency stack using a max-heap with timestamp. After executing the sequence of operations below, what is the output of the last pop() call?

fs = FreqStack()
fs.push(1)
fs.push(2)
fs.push(1)
print(fs.pop())
print(fs.pop())

easy

A. 1 and then 1

B. 2 and then 1

C. 1 and then 2

D. 2 and then 2

Solution

1. Step 1: Trace push operations

   Push 1: freq[1]=1, time=1, heap push (-1, -1, 1) Push 2: freq[2]=1, time=2, heap push (-1, -2, 2) Push 1: freq[1]=2, time=3, heap push (-2, -3, 1)

2. Step 2: Trace pop operations

   First pop: heap pops (-2, -3, 1) -> returns 1, freq[1]=1 Second pop: heap now has (-1, -2, 2) and (-1, -1, 1). Max freq is 1, tie broken by time: -2 > -1, so pop (-1, -2, 2) returns 2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Most frequent element 1 popped first, then next most recent with freq 1 is 2 [OK]

Hint: Most frequent and most recent element pops first [OK]

Common Mistakes:

• Ignoring timestamp order in heap
• Mixing up pop order when frequencies tie

2. Consider the following Python code that finds the maximum CPU load from a list of jobs. What is the value of max_load after processing all events for the input jobs = [[1,4,3], [2,5,4], [7,9,6]]?

def find_max_cpu_load(jobs):
    events = []
    for start, end, load in jobs:
        events.append((start, load))
        events.append((end, -load))
    events.sort(key=lambda x: x[0])

    current_load = 0
    max_load = 0
    for _, load_change in events:
        current_load += load_change
        max_load = max(max_load, current_load)
    return max_load

jobs = [[1,4,3], [2,5,4], [7,9,6]]
print(find_max_cpu_load(jobs))

easy

A. 7

B. 6

C. 9

D. 4

Solution

1. Step 1: List all events sorted by time:

   Events: (1,+3), (2,+4), (4,-3), (5,-4), (7,+6), (9,-6)

2. Step 2: Trace current_load and max_load through events:

   At 1: current_load=3, max_load=3; at 2: current_load=7, max_load=7; at 4: current_load=4, max_load=7; at 5: current_load=0, max_load=7; at 7: current_load=6, max_load=7; at 9: current_load=0, max_load=7.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Maximum overlap load is 7 at time 2 [OK]

Hint: Sum loads at event times, track max load [OK]

Common Mistakes:

• Off-by-one in event processing
• Ignoring negative load at job end

3. What is the time complexity of the optimal solution that sorts workers by their wage-to-quality ratio and uses a balanced tree or multiset to maintain the K smallest qualities during iteration?

medium

A. O(n log n) for sorting plus O(n log K) for balanced tree operations, total O(n log n)

B. O(n^2) due to nested loops over workers and qualities

C. O(n log n + n K) because each insertion/removal in balanced tree takes O(K)

D. O(n K) since each worker requires scanning K qualities

Solution

1. Step 1: Sorting workers by ratio

   This takes O(n log n) time.

2. Step 2: Maintaining K smallest qualities with balanced tree

   Each insertion and removal is O(log K), done for each of the n workers -> O(n log K).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n log n + n log K), dominated by O(n log n) [OK]

Hint: Sorting plus balanced tree operations dominate complexity [OK]

Common Mistakes:

• Assuming balanced tree operations take O(K) instead of O(log K)
• Confusing nested loops leading to O(n^2)
• Ignoring sorting cost

4. What is the time complexity of the optimal bucket sort approach for finding the top k frequent words from a list of n words, assuming the maximum frequency is m and average word length is constant?

medium

A. O(n log n) due to sorting all unique words

B. O(n m) because sorting words within buckets depends on max frequency m

C. O(n) because frequency counting and bucket placement are linear, and sorting within buckets is bounded

D. O(k log n) because extracting top k from a heap dominates

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies is O(n) since each word is processed once.

2. Step 2: Analyze bucket placement and sorting

   Words are placed into buckets indexed by frequency; sorting within each bucket is lexicographic but total words sum to n, so total sorting cost is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall time is linear in n with lex sort bounded by total words [OK]

Hint: Bucket sort + lex sort within buckets is O(n) total [OK]

Common Mistakes:

• Assuming full sort is needed (O(n log n))
• Confusing max frequency m as multiplicative factor
• Thinking heap extraction dominates

5. Suppose the problem changes: jobs can be reused multiple times (i.e., infinite instances of each job), and you want to find the maximum CPU load at any time considering overlaps. Which modification to the algorithm is correct to handle this scenario efficiently?

hard

A. Sort jobs by load descending and greedily add jobs until the CPU load is maximized.

B. Modify the algorithm to consider all possible combinations of job reuse, leading to exponential time.

C. Use the same sweep line algorithm without changes; reuse does not affect overlap calculation.

D. Use a dynamic programming approach to find maximum load by considering job reuse counts and intervals.

Solution

1. Step 1: Understand that infinite reuse means overlapping jobs can be repeated arbitrarily.

   Sweep line assumes fixed jobs; reuse breaks this assumption.

2. Step 2: Recognize that dynamic programming can model reuse counts and intervals to find max load.

   DP can track states with job counts and time intervals, handling reuse efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Reuse requires DP or similar, sweep line alone is insufficient [OK]

Hint: Reuse breaks fixed event model; DP needed [OK]

Common Mistakes:

• Assuming sweep line works unchanged
• Trying greedy without overlap checks