## Problem A museum has `n` exhibits. Each exhibit has a `start_time`, `end_time`, and `value`. You can visit at most one exhibit at a time and cannot overlap. Maximize the total value of exhibits visited. ```python def max_value_visits(exhibits: list[dict]) -> int: # exhibits: [{"start": int, "end": int, "value": int}] pass ``` **Example:** ``` exhibits = [ {"start": 1, "end": 3, "value": 5}, {"start": 2, "end": 5, "value": 6}, {"start": 4, "end": 6, "value": 4}, {"start": 6, "end": 8, "value": 3}, {"start": 1, "end": 8, "value": 9} ] Option A: exhibit 0 (val=5) + exhibit 2 (val=4) + exhibit 3 (val=3) = 12 Option B: exhibit 4 alone (val=9) Option C: exhibit 1 (val=6) + exhibit 3 (val=3) = 9 Output: 12 ``` ## Approach Sort by end time. Use DP: `dp[i]` = max value using exhibits 0..i where i is included. Use binary search to find the latest non-overlapping exhibit. ## Follow-ups 1. What is the time complexity of this DP with binary search? 2. If all exhibits have equal value, does this reduce to the classic activity selection problem? What is the greedy solution? 3. What if you can visit at most `k` exhibits regardless of value — how does the DP change? 4. Extend to multiple visitors who can attend different exhibits simultaneously.

InterviewDB Question

Museum Visits: Maximize Exhibits Visited Within a Time Budget Using Scheduling

Question Details

Problem A museum has n exhibits. Each exhibit has a start_time, end_time, and value. You can visit at most one exhibit at a time and cannot overlap. Maximize the total value of exhibits visited. Example: Approach Sort by end time. Use DP: dp[i] = max value using exhibits 0..i where i is included. Use binary search to find the latest non-overlapping exhibit. Follow-ups What is the time complexity of this DP with binary search? If all exhibits have equal value, does this reduce to the classic acti…

Full Details

🔒

Unlock all Karat questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a karat interview.

It covers the following topics: Coding, Greedy, Binary Search, Dynamic Programming .

Topics

Coding Greedy Binary Search Dynamic Programming

Museum Visits: Maximize Exhibits Visited Within a Time Budget Using Scheduling

Question Details

Full Details

About This Question

Topics

More Karat Interview Questions