[FEATURE]Addition of Weighted Interval Scheduling in C++ #3014
Description
Detailed description
Description:
I'd like to contribute an implementation of the Weighted Interval Scheduling problem under the Dynamic Programming section of the repository. This is a classic optimization problem where each interval has a start time, end time, and profit. The goal is to select a subset of non-overlapping intervals such that the total profit is maximized.
Although many developers are familiar with standard interval scheduling, the weighted version introduces an added layer of complexity and is an excellent example of using dynamic programming with binary search or memoization for efficiency.
What I Plan to Add
Problem Statement (clearly explained with examples)
Constraints & Assumptions (to keep it realistic and well-scoped)
Efficient Solution:
Time complexity: O(n log n) using DP + binary search
Language: Python ,C++
Test cases to ensure correctness
README or inline explanation so others can understand and learn from it
Context
Why This Is a Valuable Addition
It’s a standard DP problem that's often used in coding interviews and competitive programming.
Currently missing from many algorithm repositories.
Teaches important concepts like:
Interval sorting
Binary search for compatibility
Recurrence-based DP
Possible implementation
If it aligns with the repository’s style, I can also include a helper function to find the latest non-overlapping interval using binary search, instead of keeping that logic inside the main DP function. This keeps the implementation modular and easier to read. If preferred, I can also add a brief note or example showing how to reconstruct the selected intervals, not just the maximum profit. These are optional additions and I’m happy to follow whatever structure the maintainers prefer.
Additional information
No response