Minimum Energy to Maintain Brightness solution and explanation
The problem
You are given an integer n, representing n light bulbs arranged in a line and indexed from 0 to n - 1.
You are also given an integer brightness and a 2D integer array intervals, where intervals[i] = [starti, endi] represents an inclusive time interval during which the lighting requirement must be satisfied.
At each time unit, every bulb can independently be either on or off. A bulb that is on illuminates its own position and its adjacent positions, if they exist.
The total illumination at a time unit is the number of illuminated positions. Each position is counted at most once.
For every integer time unit covered by at least one interval in intervals, the total illumination must be at least brightness. At time units not covered by any interval, all bulbs may remain off. Each bulb that is on consumes 1 unit of energy for that time unit.
Return an integer denoting the minimum total energy required.
Example 1:
Input: n = 5, brightness = 5, intervals = [[6,12]]
Output: 14
Explanation:
- Turn on the light bulbs at positions 1 and 4.
- Current state of line:
0 1 0 0 1. - All 5 positions are illuminated, so the required brightness is reached.
- The active interval has length
12 - 6 + 1 = 7, so the total energy is2 * 7 = 14.
Example 2:
Input: n = 2, brightness = 1, intervals = [[0,0],[2,2]]
Output: 2
Explanation:
- Turn on one light bulb during each active interval.
- Each interval has length 1, so the total active time is
1 + 1 = 2. - The total energy is
1 * 2 = 2.
Example 3:
Input: n = 4, brightness = 2, intervals = [[1,3],[2,4]]
Output: 4
Explanation:
- Turn on one light bulb. It can illuminate at least 2 positions.
- The active intervals overlap, so the total active time is the length of
[1,4], which is 4. - The total energy is
1 * 4 = 4.
Constraints:
1 <= n <= 1061 <= brightness <= n1 <= intervals.length <= 105intervals[i] == [starti, endi]0 <= starti <= endi <= 109
Approach overview
Problem Overview: You are given the brightness of several lamps and a required duration they must stay lit. Brightness decreases over time, and you can spend energy to increase brightness. The task is to compute the minimum total energy required so that every lamp stays above zero brightness for the entire duration.
Approach 1: Brute Force Simulation (O(n * t) time, O(1) space)
Simulate the process minute by minute. At each step, decrease the brightness of every lamp and check if any lamp reaches zero. When a lamp is about to go dark, add energy to increase its brightness. This method directly models the process but performs repeated updates for every time unit, which becomes expensive when the required duration is large.
Approach 2: Greedy Deficit Calculation (O(n) time, O(1) space)
Instead of simulating each minute, compute how much brightness each lamp needs to survive the full duration. If a lamp starts with brightness b and must last t minutes while losing 1 unit per minute, it needs at least t brightness initially. Any deficit max(0, t - b) must be supplied as energy. Summing this deficit across all lamps gives the minimum energy required. This works because adding energy earlier or later produces the same total effect.
Approach 3: Priority Queue Maintenance (O(n log n) time, O(n) space)
If the problem allows selective recharging during the timeline, a greedy strategy with a min-heap can track which lamp will run out of brightness first. Always recharge the lamp closest to depletion. The heap stores remaining brightness and ensures the smallest value is handled first. This pattern appears frequently in greedy scheduling and priority queue problems where maintaining system stability requires handling the most critical element first.
Recommended for interviews: The deficit-based greedy solution is the expected approach. The brute-force simulation shows you understand the mechanics of the problem, but the optimized method demonstrates that you can convert a time-based process into a direct mathematical calculation. Recognizing this transformation is a common interview signal in array and greedy optimization problems.
Solution
A single bulb can illuminate at most 3 positions. To ensure the total brightness is at least brightness, the number of bulbs required to be turned on is \lceil \frac{brightness}{3} \rceil. In programming, this is commonly written in integer division form as (brightness + 2) / 3.
This problem can be solved through the following steps:
- Merge Overlapping Intervals: Merge all intervals that intersect with each other to obtain a set of mutually disjoint continuous intervals.
- Calculate Length Contribution: For each merged interval
[start, end], the number of integer points (i.e., positions) it covers ism = end - start + 1. Since every position within the interval must satisfy the minimum brightness, the total energy required for this interval is: $Energy = \lceil \frac{brightness}{3} \rceil times m - Accumulate and Sum: Accumulate the energy of all disjoint intervals to get the final answer ans
.
The time complexity is O(n log n), and the space complexity is O(n), where n$ is the number of intervals.
class Solution:
def minEnergy(self, n: int, brightness: int, intervals: list[list[int]]) -> int:
intervals.sort()
merged = [intervals[0]]
for x in intervals[1:]:
if merged[-1][1] < x[0]:
merged.append(x)
else:
merged[-1][1] = max(merged[-1][1], x[1])
ans = 0
for start, end in merged:
m = end - start + 1
ans += (brightness + 2) // 3 * m
return ansclass Solution {
public long minEnergy(int n, int brightness, int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<>();
merged.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] x = intervals[i];
int[] last = merged.get(merged.size() - 1);
if (last[1] < x[0]) {
merged.add(x);
} else {
last[1] = Math.max(last[1], x[1]);
}
}
long ans = 0;
for (int[] interval : merged) {
int start = interval[0];
int end = interval[1];
int m = end - start + 1;
ans += (brightness + 2L) / 3 * m;
}
return ans;
}
}class Solution {
public:
long long minEnergy(int n, int brightness, vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged = {intervals[0]};
for (int i = 1; i < intervals.size(); ++i) {
auto& x = intervals[i];
if (merged.back()[1] < x[0]) {
merged.push_back(x);
} else {
merged.back()[1] = max(merged.back()[1], x[1]);
}
}
long long ans = 0;
for (const auto& interval : merged) {
int start = interval[0];
int end = interval[1];
int m = end - start + 1;
ans += (brightness + 2LL) / 3 * m;
}
return ans;
}
};function minEnergy(n: number, brightness: number, intervals: number[][]): number {
intervals.sort((a, b) => a[0] - b[0]);
const merged: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const x = intervals[i];
if (merged[merged.length - 1][1] < x[0]) {
merged.push(x);
} else {
merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], x[1]);
}
}
let ans = 0;
for (const [start, end] of merged) {
const m = end - start + 1;
ans += Math.ceil(brightness / 3) * m;
}
return ans;
}func minEnergy(n int, brightness int, intervals [][]int) int64 {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{intervals[0]}
for _, x := range intervals[1:] {
if merged[len(merged)-1][1] < x[0] {
merged = append(merged, x)
} else {
if x[1] > merged[len(merged)-1][1] {
merged[len(merged)-1][1] = x[1]
}
}
}
ans := 0
for _, interval := range merged {
start := interval[0]
end := interval[1]
m := end - start + 1
ans += (brightness + 2) / 3 * m
}
return int64(ans)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * t) | O(1) | Useful for understanding the process when constraints are small |
| Greedy Deficit Calculation | O(n) | O(1) | Best general solution when total duration is known in advance |
| Priority Queue Maintenance | O(n log n) | O(n) | When recharging decisions must be made dynamically over time |
Frequently asked questions
Is Minimum Energy to Maintain Brightness easy or hard?
The problem is generally considered Medium difficulty. The challenge lies in recognizing that the time-based simulation can be converted into a direct deficit calculation, reducing the complexity from O(n * t) to O(n).
Minimum Energy to Maintain Brightness Python/Java solution
Implement a single pass through the brightness array. For each lamp, compute max(0, t - brightness[i]) and accumulate the result. This logic translates directly into Python, Java, or C++ with a simple loop and integer arithmetic.
How to solve Minimum Energy to Maintain Brightness in O(n)?
Iterate through each lamp's brightness value and compare it with the required duration t. If brightness[i] is less than t, add the difference (t − brightness[i]) to the energy cost. Summing these deficits across the array yields the minimum energy needed in linear time.
What is the best approach for Minimum Energy to Maintain Brightness?
The most efficient approach is a greedy deficit calculation. Each lamp must have at least t brightness to survive t minutes if brightness decreases by 1 per minute. The minimum energy is the sum of max(0, t − brightness[i]) across all lamps. This runs in O(n) time and O(1) space.
Is Minimum Energy to Maintain Brightness asked at Google/Amazon/Meta?
Problems with greedy deficit calculations and resource maintenance frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem title may vary, the underlying pattern of minimizing adjustments to meet constraints is common.
What data structure is used in Minimum Energy to Maintain Brightness?
The optimal solution typically uses only an array traversal with constant extra space. Some variations use a priority queue (min-heap) to always recharge the lamp closest to depletion when decisions must be made dynamically.
What is the time complexity of Minimum Energy to Maintain Brightness?
The optimal greedy solution runs in O(n) time because you only scan the brightness array once and compute deficits. Space complexity is O(1) since only a running total of required energy is maintained.