Algotree > Algorithms > Greedy > Minimum Light Bulbs Needed To Light The Whole Corridor

Minimum Light Bulbs Needed To Light The Whole Corridor

Given :

An array of N cell(s) in a jail.
Each cell has a working bulb denoted by 1 and a faulty bulb denoted by 0.
Power of each bulb is P.
A bulb with power P at position X can light cells in range [ X - P + 1, …, X + P - 1 ]
Initially all bulbs are switched OFF.

Objective : Return the minimum number of lights that should be switched ON to light the whole corridor. Return -1 if the whole corridor cannot be lighted.

Consider the below example:
Power of each bulb is 3.
Bulbs in cells [ 2, 3, 4 ] are in working condition.

Light_Bulbs

#include<iostream>
#include<vector>

using namespace std;

int solve (vector<int> &jail, int power) {

    int cells = jail.size();
    int count = 0;
    int pos = 0;
    bool lit = false;

    while (pos < cells) {

        lit = false;
        int from_right = min (cells-1, pos + power - 1);
        int from_left =  max (0, pos - power + 1);

        // Check from right
        for (int cell_no = from_right; cell_no >= pos; cell_no--) {
            if (A[cell_no] == 1) {
                count++;
                pos = cell_no + power; // new pos of the next cell to be lit.
                lit = true;
                break;
            }
        }

        if (!lit) {
            // Check from left;
            for (int cell_no = pos-1; cell_no >= from_left; cell_no--) {
                if (A[cell_no] == 1) {
                    count++;
                    pos = cell_no + power; // new pos of the next cell to be lit.
                    lit = true;
                    break;
                }
            }
        }

        if (!lit)
            return -1;
    }
    return count;
}

int main() {

    vector<int> jail1 = {0, 0, 1, 1, 1, 0, 0};
    cout << "Bulbs switched on : " << solve(jail1, 3) << endl;

    vector<int> jail2 = {1, 1, 1};
    cout << "Bulbs switched on : " << solve(jail2, 3) << endl;
  
    vector<int> jail3 = {0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0};
    cout << "Bulbs switched on : " << solve(jail3, 12) << endl;

    vector<int> jail4 = {0, 1, 0};
    cout << "Bulbs switched on : " << solve(jail4, 1) << endl;

    return 0;
}

Output

Bulbs switched on : 2
Bulbs switched on : 1
Bulbs switched on : 2
Bulbs switched on : -1

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"Before software can be reusable it first has to be usable. - Ralph Johnson"