šŸŽBACK-TO-SCHOOL DEAL. Subscribe Now to get 40% OFF at only 8.49 USD/month, only valid until Sep 30th, 2024

Question

Question
Description CS city hires M workers who drive water trucks. They spray water on the streets to clean them, and reduce the dust concentration. There are streets in CS city. The city has a dust control plan, which uses a task scheduler to generate a daily cleaning plan. This plan tells each worker what streets they are responsible for, and ideally all streets will be cleaned. For example, the plan tells worker A to clean street 0 to street , worker to clean streets . This plan will clean 7 streets. However, the task scheduler is buggy. Today it tells worker A to clean streets and tells worker B to clean streets [3, 5]. Someone realizes that two workers cleaned street 3 twice, and no one cleaned street 6. It's your job to write a program to automatically detect the task scheduler's bugs, and report how many streets are not cleaned in today's plan. Input Format The first line contains two integers . is the number of workers, and is the number of streets. The following lines are just the plan generated by task scheduler. Each line contains two integers , ]. It indicates that worker i should clean street to . Output Format One integer, representing how many streets have not been cleaned. Sample Input 27 Sample Input 27 03 35 Sample Output 1 Explanation Worker A cleans streets [0,3], and worker B cleans streets [3,5]. Street 6 is the only street that was not cleaned, so return 1. Input Constraints

Asked By EnchantedEcho88 at

Answered By Expert

Shawn

Expert Ā· 2.1k answers Ā· 2k people helped

Step 1/4

In this question, we have M workers and N streets to clean.

Each worker is assigned a set of streets in sequential order but due to a bug, sometimes the streets assigned get overlapped or some street gets left out.

We need to find how many streets got left out.

Step 2/4

First we take an array 'a' of size 2 to store the start and end street numbers of every worker.

Then we take an empty array named 'h' with all elements as 0.

We take input from user for the values of m and n.

Step 3/4

Now we take a for loop starting from 0 till m (number of workers)

Inside the loop, we input the values of start and end street number from the user into a[0] and a[1] respectively.

Now we take an inner loop starting from start street number or a[0], ending at end street number or a[1] (inclusive) and then for the values found inside this range, we change the corresponding value in the 'h' array from 0 to 1.

In other words we mark the streets covered (from start till end for every worker) by making their values as '1' in the 'h' array which initially contained '0'.

Step 4/4

in the end, we take another loop starting from 0 till the total number of streets.

we check if in the 'h' array there is an element whose value is still 0, that means that street hasn't been assigned to any worker.

if the value is 0, we count how many 0's are there in a variable count.

Final Answer

Final Code:

Input:

2 7

0 3

3 5

Output:

1