Number of occurences of each term

问题:

I'm given an array a[n][2], where n can be 10^5 at max. There are n subjects and n students. All numbered 1, 2, ..., n.

a[i][0] and a[i][1] (1 <= i <= n) denote that in i-th subject, all students from a[i][0] to a[i][1] passed, while the rest didn't. I'm supposed to find the number of subjects each student passed in.

For eg.,

n=5 and a = [ [1,3], [1,3], [1,5], [1,5], [1,5] ] 

should give output

[5, 5, 5, 3, 3]

(2)

n = 10, a = [ [1,10], [1,10], [1,10], [3,5], [1,10], ..., [1,10] ]

The expected answer should be

[ 9, 9, 10, 10, 10, 9, 9, 9, 9, 9]

回答1:

Didn't quite understand your code, here is an alternative approach. This is similar to an interval problem. Let's take your example:

• n = 5
• a = [ [1,3], [1,3], [1,5], [1,5], [1,5] ]

We first make an array of size as no. of subjects + 1 (for the sake of simplicity in computation).

1   2   3   4   5   6

• Now, let's go through intervals one by one. Whenever we come across an interval, we add +1 to the starting point and -1 to the ending point + 1^th location.

Array representation:(after the entire above process).

 1          2          3          4         5         6

+1                               -1                           [1,3]
+1                               -1                           [1,3]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]

• All is pending is to just start summing from left to right and you get your answers for each student. The above process works because we negate( as in do a -1) the addition after the last student for each interval since the further students didn't pass that particular subject. So, while summing, we are bound to get the right total for each student.

Summing looks like:

 1          2          3          4         5         6

+1                               -1                           [1,3]
+1                               -1                           [1,3]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]
+1                                                   -1       [1,5]

 5          5          5          3         3         0(not considered anyway)