AlgoGenesis / C

AlgoGenesis is a centralized open-source platform dedicated to providing optimized and well-documented algorithm implementations in C. Perfect for both beginners and advanced users, this repository serves as a comprehensive learning resource for solving algorithmic challenges.
MIT License
89 stars 278 forks source link

[NEW ALGORITHM] Painter's Problem (Binary Seearch) #1522

Open mansi066 opened 4 hours ago

mansi066 commented 4 hours ago

Issue will be closed if:

1) You mention more than one algorithm. You can create a separate issue for each algorithm once the current one is completed.
2) You propose an algorithm that is already present or has been mentioned in a previous issue.
3) You create a new issue without completing your previous issue.

Note: These actions will be taken seriously. Failure to follow the guidelines may result in the immediate closure of your issue.


Name:

[NEW ALGORITHM] Painter's Problem

About:

Painter's Partition Problem: Imagine you have n boards and k painters. Each painter can paint one contiguous block of boards in one unit of time. The task is to minimize the maximum time taken by any painter.

Objective: Minimize the maximum time taken by any painter to paint all the boards.

Binary Search Approach: To solve this using binary search, you follow these steps:

Search Space:

The minimum possible time is the maximum length of a single board (i.e., max(boards)).

The maximum possible time is the sum of all board lengths (i.e., sum(boards)).

Binary Search:

Perform binary search within the defined search space.

The middle value (mid) represents a candidate for the minimum possible maximum time.

Feasibility Check:

Check if it's possible to paint all boards within mid time using k painters.

If possible, adjust the search space to find a smaller possible maximum time.

If not possible, adjust to find a larger possible maximum time.

Labels:

new algorithm, gssoc-ext, hacktoberfest, level2


Assignees:

github-actions[bot] commented 4 hours ago

👋 Thank you for raising an issue! We appreciate your effort in helping us improve. Our team will review it shortly. Stay tuned!

mansi066 commented 4 hours ago

@pankaj-bind please assign me