Last Updated: 13 Nov, 2020

PAINT THE FENCE

Easy

Asked in companies

Solve now

Problem statement

You have a long fence in your backyard. The fence consists of 'N' sections, each of them made from a different material.

The fence is not painted yet, so you decide to hire 'Q' painters to paint it. The i-th painter will paint all the sections lying in the section range [Li, Ri].

Unfortunately, you are on a tight budget, so you decided to hire only 'Q' - 2 painters. Now, you want to maximise the number of painted sections in your fence, so you have to choose those 'Q' - 2 painters optimally.

Note:

A section is considered painted if at least one painter paints it.

Input Format:

The first line of the input contains two positive integers ‘N’ and ‘Q’ which represent the length of the fence and number of painters, respectively.

From the second line, the next ‘Q’ lines represent the range of sections of the fence that i-th painter can paint. Every range contains two single space-separated integers representing 'Li' and 'Ri', respectively.

Output Format:

The only line of output will print an integer denoting the maximum number of painted sections if you hire 'Q' - 2 painters optimally.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

3 <= N <= 1000
3 <= Q <= 500
1 <= Li <= N 
Li <= Ri <= N  

Time limit: 1 sec

Solve now

Approaches

01 Approach

We will consider each pair of painters using two nested loops and count all the sections that can be painted by removing each pair of painters.

Out of all the pairs, we will pick one which will result in maximum painted sections.

Solve now

02 Approach

The problem boils down to finding the sections that could remain unpainted if we remove 2 painters and then subtracting the minimum of them from the total sections that can be painted by all painters.

Following is the algorithm for this approach:

We will create a 2d array/list ‘SECTION’ where ‘SECTION[i]’ contains all painters who can paint the i-th section.
We will maintain ‘TOTAL’ to find all sections that can be painted by all painters together.
Then, we make a 2D array 'COUNT' where 'COUNT[i][j]' denotes the number of sections that will remain unpainted if ‘i’ and ‘j’ painters will be removed.
Loop over all arrays/lists of the ‘SECTION’ array.
1. If ‘SECTION[i]’.size() == 1
  1. Then for all ‘j’ != ‘SECTION[i][0]’, perform ‘COUNT[SECTION[i][0]][j]++’ and ‘COUNT[j][SECTION[i][0]]++’.
  2. This is because ‘SECTION[i]’ can only be painted by one painter ‘SECTION[i][0]’. So if we remove the painter ‘SECTION[i][0]’, then ‘SECTION[i]’ will remain unpainted.
  3. Hence, we pick all pairs of painters that include one painter as ‘SECTION[i][0]’ and increment the ‘COUNT[SECTION[i][0][j]’ and ‘COUNT[j][SECTION[i][0]’ by 1.
2. If ‘SECTION[i].size()’ == 2
  1. Then perform ‘COUNT[SECTION[i][0]][SECTION[i][1]]++’ and ‘COUNT[SECTION[i][1]][SECTION[i][0]]++’.
  2. This is because ‘SECTION[i]’ can only be painted by two painters ‘SECTION[i][0]’ and ‘SECTION[i][1]’. So if we remove both painters then, ‘SECTION[i]’ will remain unpainted.
  3. Hence, we are incrementing ‘COUNT[SECTION[i][0]][SECTION[i][1]]’ and ‘COUNT[SECTION[i][1]][SECTION[i][0]]’ by 1.

5. Finally, Return ‘TOTAL’ - minimum of ‘COUNT’ array/list.

Solve now

03 Approach

In this approach, we will try to optimize approach 1. We will use the prefix sum array to reduce the time complexity.

Following is the algorithm for this approach:

We will create a ‘SECTION’ array where ‘SECTION[i]’ represents the number of painters that could paint the i-th Section.
We will create two arrays ‘SINGLE_PAINTER’ and ‘DOUBLE_PAINTER’ where-
1. ‘SINGLE_PAINTER[i]’ represents the number of Sections from starting till the i-th Section that could be painted by only one painter.
2. ‘DOUBLE_PAINTER[i]’ represents the number of Sections from starting till the i-th Section that could be painted by only two painters.
We will have ‘total’ as the number of Sections that can be painted by all painters together.
Consider each pair of painters using two for loops.
We will maintain ‘CURR_ANS’ which will be storing the number of Sections that can be painted by painters after removing i-th and j-th painter.
‘CURR_ANS’ can be calculated in constant time.
1. ‘CURR_ANS’ is ‘total’ - (Sections that can be only painted by the painter ‘i’) - (Sections that can be only painted by the painter ‘j’).
2. Let the common range between [li, ri] and [lj, rj] be [l, r].
3. Now we will add (SINGLE_PAINTER [r] - SINGLE_PAINTER [l-1]) in ‘CURR_ANS’.
  1. This is because we considered this Section [l, r] twice during subtraction.
4. Then, subtract (DOUBLE_PAINTER [r] - DOUBLE_PAINTER [l-1]) from ‘CURR_ANS’.
  1. This is because the Section [l, r] that could be painted by only two painters will become unpainted after removing ‘i’ and ‘j’ painters.
5. We will be maintaining the maximum of ‘CURR_ANS’ in ‘MAX_PAINTED’.
Finally, return ‘MAX_PAINTED’.

Solve now