c# - 找到给定的不等式集的最大子集，它有一个解决方案

Question

我是新来的，这是我的第一个问题。那么，直接进入正题。我有一个我无法解决的任务，如果有人能为我提供解决方案的指导，我会很高兴。主要问题是我无法完全理解我的最终输出应该是什么。

这是任务:

给定一组不等式。每个不等式都引用变量 X。确定给定集合中具有解的最大子集。输入文件 inequalities.in 将包含最多 50 个不等式的列表，每行一个不等式。每个不等式以下列形式之一给出:“X < C”、“X <= C”、“X = C”、“X > C”或“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

您描述的问题是找到基数最大的 clique在interval graph .更准确地说，输入的每一行都描述了实线上的一个区间。不失一般性，半闭区间可视为闭区间；通过处理输入，可以搜索最大和最小边界(例如 min 和 max)，并且每个半闭区间可以由相应的值封闭，如下所示。

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

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

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