Problem

Submissions

Hints & solutions

Discuss

PAINT THE FENCE

Easy

0/40

Average time to solve is 20m

Contributed by

110 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample output 1:

Explanation of Sample output 1:

One of the best ways to choose three painters is to select 1st, 3rd and 4th painter. Together, the three can paint the whole wall.

Sample Input 2:

Sample output 2:

Hint 1

Hint 2

Hint 3

Try to remove each pair of painters and check which yields maximum output.

Approaches (3)

Approach 1

Approach 2

Approach 3

BRUTE FORCE

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.

Time Complexity

O(N * Q * Q), where ‘N' is the length of the fence, and ‘Q’ is the number of painters.

Since we are iterating for every pair of painters and then linearly checking the total sections that can be painted without them, the time complexity is O(N * Q * Q).

Space Complexity

O(N), where 'N' is the length of the fence.

This is the space used by the ‘SECTION’ array, which will be used to calculate the number of painters that can paint the i-th section.

(75% EXP penalty)

(100% EXP penalty)

PAINT THE FENCE

Console