3413.maximum-coins-from-k-consecutive-bags.md

3413. Maximum Coins From K Consecutive Bags

Greedy

To obtain the maximum coins, the k consecutive bags should align to the beginning or end of one of the intervals. (Greedy)

// k is aligned the beginning of the interval[i]
|--3--|  |--5--|  |---4---|
         ^
         |____k______|

// or to align the end of the interval[i]
|--3--|  |--5--|  |---4---|
               ^ // k is aligned in the end of the interval[1]
   |_____k_____|

Why? Let's consider the following counter-examples:

• Case 1: The start (end) of k is not in the interval. There is some empty coins wasted, we must move k to align the start or end of the interval.

   |--5--|  |---4---|
 |______k______|
 ^^^ // Empty coin, wasted

// We move the start of `k` to align the start of the interval[i]
   |--5--|   |---4---|
   |______k'_____|

// --------------------------------------------
// Or the end of `k` is not in the `interval[i]`:
   |--5--|   |---4---|
           |______k______|
                      ^^^^ // Empty coin, wasted

// Or we move the end of `k` to align the end of the interval[i]
   |--5--|   |---4---|
       |______k'_____|

• Case 2: The start and end of k are in the interval (but not align the beginning (end) of the interval). We can move to align the start or end of interval to gain more coins potentially. For example, we can move k to align the start of the interval to gain more 5 even we lose some 3.

|--5--|  |-----| |---3---|
   |_______k_______|
<---
|_______k'______|