Find the maximum number of purple cars possible in the given sequence of N cars.(See description) [closed]

Question

There are N cars in a row numbered from 1 to N. A person takes M photographs of cars. For each photograph, the cars appearing in it are given by tuple (i, j), which means all the cars from ith car to jth car will appear in that photograph.

Note that, all the photos need not cover every car. A car can appear in more than one photograph.

It is given that each photograph contains exactly 1 purple car. Find the maximum number of purple cars possible. If not possible print -1.

Input : First line contains N and M. Next line contains M pairs (x, y) which represent a photograph containing cars from xth car to yth car. Output : Maximum number of purple cars possible.

Example :

Input:

5 1

(3 5)

Output : 3

Explanation : only one car from 3 to 5 can be purple. Car 1 and car 2 will be purple for maximizing the number of purple cars.

Input:

5 1

(4 4)

Output : 5

Input:

5 3

(1 4), (3 5), (3, 4)

Output : 1

Explanation : Either 3 or 4 can be a purple car.

Input:

5 2

(1, 4), (2, 5)

Output : 2

Explanation: Car 1 and Car 5 can be purple.

Input :

10 3

(1 5), (6, 10), (1, 10)

Output: -1

Explanation: It is impossible in this case for each interval to have exactly 1 purple car.

Answer 1

If I'm not mistaken, the problem can be solved as a network problem as follows.

The node set of the network has a source node s and a terminal t; imagine the sink at a leftmost position and the terminal in the righmost position and the flow goes from left to right. Next to s put a node for each car and connect s to every car. Next to the car nodes create a node for each interval. Now start at the car nodes and create paths to t, traversing the interval node set; the path goes through every interval which contains the car.

Except for s and t, the flow in each node is restricted to be exactly 1 which models that exactly 1 car per interval must be colored purple; the arcs do not explicitly need to be constrained. Finally via some network flow algorithm, maximize the intensity of the flow from s to t. Color each car purple for which its node has a nonzero flow. If the instance does not permit a feasible flow, the initial problem instance is infeasible.

Answer 2

Notice that, if there is a photograph which is totally covered by another photograph, we only need to care about the outer photograph(trivial).

Second observation:

For now, after removing all covered photographs (as stated above), we will be left with cases like this:

We have n photographs, it can be divided into several clusters, with each cluster is a group of m photographs: (a1, b1) , (a2, b2) ... , (am, bm) with a1 < a2 and b1 > a2 ... or ai < a(i + 1) and bi > a(i + 1)

We notice that, it is always optimal if we select the first purple car for the first photograph to be in the range (a1, a2), and continue to select car in this manner (the first range which is not yet covered by any car). Prove:

• if we select car in range (a1, a2), so the next car can be selected will be in range (b1 , bm), otherwise, if we choose other car (in range (a2,b1)), the range to select next car will be smaller range (trivial to see), so , select car in range (a1, a2) will give optimal result.

If we implement a sweep line algorithm, time complexity will be O(m log m)

Note: this algorithm is valid only if the set of photographs is valid, otherwise, we need to check for its validity.

Update : As pointed out by PeterdeRivaz, we need to take care of one special case: when there are two or more photographs, both cover one photographs, so, we need to join all of them.