PAINT THE FENCE

Posted: 13 Nov, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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
Approach 1

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.

Try Problem