首页 > 代码库 > 贪心算法选择不相交区间

贪心算法选择不相交区间

2024-08-18 05:35:12   217人阅读

Input
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。
 
Output
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。
 
Sample Input
12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0
 
Sample Output
5
 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int n,count,temp;
 6     int a[100], b[100];
 7     while (cin >> n&&n)
 8     {
 9         count = 1;
10         for (int i = 0; i < n; i++)
11         {
12             cin >> a[i] >> b[i];
13         }
14         for (int i = 0; i < n; i++)
15         {
16             for (int j = i; j < n; j++)
17             {
18                 if (b[j] < b[i])  { temp = b[i]; b[i] = b[j]; b[j] = temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }
19             }
20         }
21         int k = 0;
22         for (int i = 1; i < n; i++)
23         {
24             if (a[i] >= b[k])  { count++; k = i; }
25         }
26         cout << count << endl;
27     }
28     return 0;
29 }

运用贪心算法，把结束时间从小到大排序，看越早结束的节目就能看的越多，之后按照开始时间一个个选择即可。

贪心算法选择不相交区间


联系
我们