C#贪婪算法，用于选择不冲突的活动(更正)
我的任务是贪婪的算法：
活动选择问题是这类问题的特征，目标是选择最大数量的不相互冲突的活动。
示例输入(第一行表示间隔的数目；后面的每一行包含一个开始时间和结束时间)：
5
2 4
1 7
6 9
9 11
5 8相应的输出(不重叠活动的最大数量，然后是这些活动的索引)：
3
1 5 4上述产出表明，每隔2-4、5-8和9-11时间间隔的活动都可以选择，没有重叠。
这个程序在小数据上工作，但是速度太慢，无法进行大的输入，我不知道如何改进它。有什么想法吗？
class Program
{
static void Main(string[] args)
{
int N;
int[,] a;
using (StreamReader sr = new StreamReader(@"prednasky.in"))
{
string line;
line = sr.ReadLine();
N = int.Parse(line);
a = new int[N, 2];
int[] indx = new int[N];
int[] b = new int[N];
for (int i = 0; i < N; i++)
{
line = sr.ReadLine();
int[] nums = line.Trim().Split().Select(int.Parse).ToArray();
//the beginning of the interval to a[i, 0], indexes to a[i, 1]
a[i, 0] = nums[0];
a[i, 1] = i + 1;
//The end of the interval to b[i]
b[i] = nums[1];
//indx is array of indexes, i sort it instead of array a
indx[i] = i;
}
//now sort array of the end of the interval and array of indexes by it
Array.Sort(b, indx);
//now in 1 cycle going through a[index, *] and b. And save "correct" intervals to the start of a(becouse we already don't need it
int last = 0;
int poc = 0;
for (int i = 0; i < N; i++)
{
if (a[indx[i], 0] > last)
{
a[indx[poc], 0] = a[indx[i], 1];
poc++;
last = b[i];
}
}
using (StreamWriter sr1 = new StreamWriter(@"rozvrh.out"))
{
sr1.WriteLine(poc);
for (int i = 0; i < poc; i++)
{
sr1.Write(a[indx[i], 0]);
sr1.Write(" ");
}
}
}
}
}回答 1
Code Review用户
发布于 2017-03-09 19:45:51
C#代码开发的流行规则之一是，您的代码应该为其他人所读。这意味着，您所做的事情的意图应该由阅读您的代码的其他人轻松地确定。
你的帖子不是这样的。
我甚至不能开始评论你的算法，而不花很多时间来弄清楚你在做什么。因此，我的回答是关于风格和结构的。
不要把所有东西都放在Main()*你的应用程序想做3件事情：
- 读取输入
- 经过计算
- 写输出
你的主要任务将沿着这些职责分工简化。因此，您的新Main()将：
- 调用读取和验证输入的方法。
- 调用基于验证输入执行计算的方法。
- 调用执行输出的方法
为您的对象选择更好的名称。a，b，和indx告诉我的东西很少，很难理解。尤其是带有indx和指向indx的概念。C#具有非常现代的特性，比如类。类似于：
public class Interval
{
public int Start { get; set; }
public int End { get; set; }
}使用指向另一个数组的指针丢弃。我认为没有理由使用a[indx[i], 0]。在使用类或结构时，没有理由使用多维数组。
想象一下，遵循您的逻辑是多么容易，而不是神秘地使用：
last = b[i];在这样的情况下，人们很容易对b[i]失去兴趣，并想知道last意味着什么(例如，它是指数组中的最后一个元素还是您使用的最后一个值)，您可以在名为intervals的变量中使用List<Interval> (或者如果您坚持使用Interval[])，您可以使用：
largestEnd = intervals[i].End;对一个人来说听你的意思就容易多了。一旦他们能够遵循这一点，他们将更好地定位于对算法进行评论。
https://codereview.stackexchange.com/questions/157320
复制相似问题
腾讯云开发者
