2014
11-15

# Problem B. GBus count-Google APAC 2015

Problem B. GBus count

There exists a straight line along which cities are built.

Each city is given a number starting from 1. So if there are 10 cities, city 1 has a number 1, city 2 has a number 2,… city 10 has a number 10.

Different buses (named GBus) operate within different cities, covering all the cities along the way. The cities covered by a GBus are represented as ‘first_city_number last_city_number’ So, if a GBus covers cities 1 to 10 inclusive, the cities covered by it are represented as ’1 10′

We are given the cities covered by all the GBuses. We need to find out how many GBuses go through a particular city.

### Input

The first line contains the number of test cases (T), after which T cases follow each separated from the next with a blank line.
For each test case,
The first line contains the number of GBuses.(N)
Second line contains the cities covered by them in the form
a1 b1 a2 b2 a3 b3…an bn
where GBus1 covers cities numbered from a1 to b1, GBus2 covers cities numbered from a2 to b2, GBus3 covers cities numbered from a3 to b3, upto N GBuses.
Next line contains the number of cities for which GBus count needs to be determined (P).
The below P lines contain different city numbers.

### Output

For each test case, output one line containing “Case #Ti:” followed by P numbers corresponding to the number of cities each of those P GBuses goes through.

Input
2
4
15 25 30 35 45 50 10 20
2
15
25
10
10 15 5 12 40 55 1 10 25 35 45 50 20 28 27 35 15 40 4 5
3
5
10
27
Output
Case #1: 2 1
Case #2: 3 3 4

1 <= ai <= 5000, 1 <= bi <= 5000

for(int i=a; i<=b; i++) cntArr[i]++;

cntArr[a]++;   cntArr[b+1]–;

/**
* Created by GaoTong on 2014/11/9.
*/
public class GBusCount {
static Scanner s = null;
static int n;
static final int MAXN = 5005;
static int cntArr[];

public static void main(String args[]) throws FileNotFoundException {
s = new Scanner(System.in);
int c = s.nextInt();

for(int k=1; k<=c; k++){
int n = s.nextInt();
cntArr = new int[MAXN];
int minVal = MAXN;
int maxVal = -1;
for(int i=0; i<n; i++){
int a = s.nextInt(); //the start station
int b = s.nextInt(); //the end station
if( minVal > a) minVal = a;
if(maxVal < b) maxVal = b;
cntArr[a]++;
cntArr[b+1]--;
}
for(int i=1; i<=maxVal; i++)
cntArr[i] += cntArr[i-1];

int p = s.nextInt();
System.out.print("Case #" + k + ":");
while(p-- > 0){
int point = s.nextInt();
if( point < minVal || point > maxVal)  System.out.print(" 0");
System.out.print(" " + cntArr[point]);
}
System.out.println();
}
}
}

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

3. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;