Article directory
- 1. Venue arrangement issues
-
- 1.1 Problem description
- 1.2 Idea analysis
- 1.3 Example analysis
- 1.4 Code writing
- 2. Optimal service order problem
-
- 2.1 Problem description
- 2.2 Idea analysis
- 2.3 Code writing
1. Venue arrangement issues
1.1 Problem description
?Suppose you schedule a batch of events in enough venues and want to use as few venues as possible. Design an efficient greedy algorithm for scheduling.
data input:
No.1
1
There is an integer in row 1
n
n
n, means there is
n
n
n events to be scheduled. Next
n
n
In n lines, each line has
2
2
2 positive integers, respectively representing
n
n
The start and end times of n to-be-scheduled activities. Time starts with
0
0
Minutes starting at 0 o’clock.
Data output:
Calculate the minimum number of venues and output it.
1.2 Idea analysis
?1. Greedy strategy: Use the venue with the earliest end time as the greedy choice.
?2. Use arrays
s
s
s and
f
f
f Store the start time and end time of each activity separately.
- will array
s
s
s sorting, which is the order in which venues are selected for each activity.
- will array
f
f
f sort. Since the end time of the venue is determined by the end time of the activity, the sorted array is also the end time of the venue.
?3. (1) First open a venue for the activity that starts earliest. At this time, the earliest end time of the venue is the end time of the activity. (2) Then traverse the remaining activities. For each activity, determine whether there are still activities in the venue that ends earliest: if so, open a new venue; if not, it means that the venue that ends earliest can accommodate the current activity, and update the end time of the venue to ensure the earliest end. The venue will be the first to start the next activity.
1.3 Example analysis
?Has
4
4
There are 4 activities, the start and end times of each activity are {1, 6}, {4, 8}, {9, 10}, {7, 18} respectively.
Some students may be confused: How come the start time and end time of each activity are sorted separately? Then isn’t the correlation between the start time and end time of each activity broken? How can related things be sorted?
Answer: This question does not need to be related. For this solution, you only need to care about the start time and end time, as long as the maximum end time and the current start time in the set are enough.
1.4 Code Writing
Sample input:
5
1 23
12 28
25 35
27 80
36 50
Sample output:
3
The time complexity is
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#include<bits/stdc + + .h>
using namespace std;
int main(){<!-- -->
int n;
cout<<"Please enter the number of activities:"<<endl;
cin>>n;
\t
int s[n],f[n];
cout<<"Please enter the start time and end time of each activity:"<<endl;
for(int i=0;i<n;i + + )
{<!-- -->
cin>>s[i]>>f[i];
}
\t
sort(s,s + n);//understand why ascending order is required
sort(f,f + n);
\t
//The shortest end time order of the venue is represented by j, and the activities to be allocated are traversed by i
int j=0,ans=0;
\t
for(int i=0;i<n;i + + )
{<!-- -->
if(s[i] < f[j])
{<!-- -->
ans + + ;
}
else
{<!-- -->
j + + ;
}
}
cout<<"The minimum number of venues is:"<<ans<<endl;
return 0;
}
2. Optimal service order problem
2.1 Problem description
?Has
n
n
n customers are waiting for a service at the same time. customer
i
i
i The required service time is
t
i
t_i
Ti?,
1
≤
i
≤
n
1≤i≤n
1≤i≤n. How should it be arranged
n
n
The service sequence of n customers can minimize the average waiting time? The average waiting time is
n
n
The sum of n customers’ waiting time divided by
n
n
n. for a given
n
n
The service time required by n customers is programmed to calculate the optimal service order.
data input:
No.1
1
1 row is a positive integer
n
n
n, means there is
n
n
n customers. Next
1
1
In 1 row, there is
n
n
n positive integers, representing
n
n
The service time required by n customers.
Data output:
Output the corresponding minimum average waiting time and retain2
2
2 decimal places.
2.2 Idea analysis
?Greedy strategy: Customers with shorter service times complete their business first, which will minimize the total waiting time.
2.3 Code writing
Sample input:
10
56 12 1 99 1000 234 33 55 99 812
Sample output:
532.00
#include<bits/stdc + + .h>
using namespace std;
int main()
{<!-- -->
int n;
cout<<"Please enter the number of customers:"<<endl;
cin>>n;
\t
int a[n];
cout<<"Please enter the time each customer needs service:"<<endl;
for(int i=0;i<n;i + + )
{<!-- -->
cin>>a[i];
}
\t
sort(a,a + n); //Sort each customer's waiting time in ascending order
\t
int sum=0;
int num=n; //There are num people left waiting for the person currently handling business.
for(int i=0;i<n;i + + )
{<!-- -->
sum = sum + num*a[i]; //The person receiving the service is actually waiting for his service to end
num--;
}
cout<<"The average waiting time is:"<<endl;
double ans=sum/n;
cout<<fixed<<setprecision(2)<<ans<<endl;
return 0;
}
