Welcome to Subscribe On Youtube
3951. Minimum Energy to Maintain Brightness
Description
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
Solutions
Solution 1: Interval Merge
A single bulb can illuminate at most 3 positions. To ensure the total brightness is at least $\textit{brightness}$, the number of bulbs required to be turned on is $\lceil \frac{\textit{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 is $m = end - start + 1$. Since every position within the interval must satisfy the minimum brightness, the total energy required for this interval is: \(\text{Energy} = \lceil \frac{\textit{brightness}}{3} \rceil \times m\)
- Accumulate and Sum: Accumulate the energy of all disjoint intervals to get the final answer $\textit{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 { 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; } }; -
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 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) } -
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; }