Class notes (4) (3) -573. Lecture hall arrangement (Hall)

Catalog ：

Description

Format

Input

Output

Samples

input data 1

Output data 1

Limitation

Hint

Answer key ：

Program  

Description

There is a lecture hall that we need to manage , The speakers set the starting time and ending time of the speech in advance . We want to maximize the use of the lecture hall . We have to accept some reservations and reject others , The goal is to make speakers use the hall the longest . Suppose at some point a speech ends , Another speech can start immediately .

【 Programming tasks 】

1、 Enter the speaker's Application .

2、 Calculate the maximum possible use time of the lecture hall .

3、 Output the result .

Format

Input

Enter the first line as an integer N(N≤5000), Indicates the number of applications .

following  n Each line contains two integers p,k(1≤p<k≤30000), Indicates the start time and end time of this application .

Output

The output contains an integer , Indicates the maximum possible use time of the hall .

Samples

input data 1

12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20

Output data 1

16

Limitation

1s, 1024KiB for each test case.

Hint

The time of each activity here is “ End time - Starting time ”.

Answer key ：

It's a disguised examination 0/1 knapsack , Add a structure, get a reorganization function, and then sort .

Program ：

#include <bits/stdc++.h>
using namespace std;
int n,dp[30010];// The number of arrays is the maximum end time  
struct T{
	int b,e,ans;//b It's the start time (begin),e It's the end time (end),ans For the use time of the application  
	bool operator<(const T &B)const{
		return e<B.e||(e==B.e&&b<=B.b); 
	}
}a[5010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].b>>a[i].e;
		a[i].ans=a[i].e-a[i].b;// Calculate usage time  
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)// Traverse n Applications  
		for(int j=a[n].e;j>=a[i].e;j--)
			dp[j]=max(dp[j],dp[a[i].b]+a[i].ans);
	cout<<dp[a[n].e];
    return 0;
}