求有解的给定不等式集的最大子集

Question

我是新来的，这是我的第一个问题。所以，直接谈到这个话题。我有一个我无法解决的任务，如果有人能为我提供解决方案的方向，我会很高兴。主要的问题是我不能完全理解我的最终输出是什么。

这是我们的任务：

你会得到一组不等式。每个不等式都涉及变量X。确定给定集合中有解的最大子集。输入文件inequalities.in将包含最多50个不等式的列表，每行一个不等式。每个不等式都以下列形式之一给出：“XC”或“X >= C”，其中C是某个整数常数(对于不同的不等式，可能是不同的)。输入的数据将是正确的，不需要显式检查。在输出文件的第一行，inequalities.out打印整数K:可以同时满足的不等式的最大数目。在下面的K行中打印找到的一组不等式，每行一个不等式，而不考虑它们的顺序。

样本输入

X >= 3

X<5

X<6

X >= 3

X= 100

X<3

X>3

X <= -1

样本输出

5

X >= 3

X<5

X<6

X >= 3

X>3

解释

当X=4时，这五个不等式都成立。没有更大的子集有解。

下面是我的代码：

class Program
{
 static void Main(string[] args)
 {
  Console.Write("Enter X: ");
  int x = int.Parse(Console.ReadLine());
  List<string> result = ParseInequalities.Parse(x);

  Console.WriteLine("\nCount of inequalities is: {0}", result.Count);
  foreach (var item in result)
  {
   Console.WriteLine(item);
  }

 Console.ReadLine();
 }
}

public static class ParseInequalities
{
 public static List<string> Parse(int x)
 {
  List<string> inequalities = new List<string>();
  using (StreamReader reader = new StreamReader(@"D:Sample.txt"))
  {
   string line = "";
   while ((line = reader.ReadLine()) != null)
   {
    string[] parts = line.Split(' ');

    if (parts[1] == "=")
    {
      if (x == Convert.ToInt32(parts[2]))
      {
       inequalities.Add(line);
      }
    }
    else if (parts[1] == ">=")
    {
     if (x >= Convert.ToInt32(parts[2]))
     {
      inequalities.Add(line);
     }
    }
    else if (parts[1] == ">")
    {
     if (x > Convert.ToInt32(parts[2]))
     {
      inequalities.Add(line);
     }
    }
    else if (parts[1] == "<")
    {
     if (x < Convert.ToInt32(parts[2]))
     {
      inequalities.Add(line);
     }
    }
    else if (parts[1] == "<=")
    {
     if (x <= Convert.ToInt32(parts[2]))
     {
      inequalities.Add(line);
     }
    }

  }
  return inequalities;
  }
 }

}

这是一个解决方案，但显然不是应该提供的解决方案。也许我必须从不同的角度看，但我缺乏想法。

我的英语不是很好，但我希望你能理解我，

谢谢

Answer 1

您所描述的问题是在interval graph中寻找基数最大的clique。更准确地说，输入的每一行都描述了实数行上的一个间隔。在不损失一般性的情况下，半闭区间可被视为闭合区间；通过处理输入，可搜索最大和最小边界(例如min和max)，并且每个半闭区间可按各自的值闭合，如下所示。

X > C => max + 1 > X > C
X < C => min - 1 < X < C

这些区间构成了图的节点集；当且仅当两个节点相交时，它们才由一条边连接。问题是在这个图中找到一个尽可能大的集团，并且可以在与图的节点相关联的区间的交集中找到所需的值X。

根据this publication的说法，有一种具有运行时绑定O(n log n)的算法来确定基数最大团，尽管在一般图中找到团是NP-hard。

Answer 2

我将为所有出现的数字创建一个排序列表：-1，3，5，6,100

然后在每个间隔中选择任意一个X：-1.5、2、4、5.5、50、150

对于两个列表中的所有数字，检查哪一个满足最多的不等式。

运行时是O(n^2)而不是O(n logn)，但对于50个不等式，这可能已经足够好(而且简单得多)。