The maximum subsets of intervals that do not exceed the coverage limit?

Question

Here is one of the coding issues I'm confused about.

For a two-dimensional array, [[1, 9], [2, 8], [2, 5], [3, 4], [6, 7], [6, 8]]each inner array is an interval; and if we accumulate these intervals, we will see:

1 2 3 4 5 6 7 8 9
  2 3 4 5 6 7 8
  2 3 4 5 
    3 4   
          6 7
          6 7 8

Now there is a limit according to which the coverage should be <= 3 for each position; and obviously we could see position 3, 4, 6, 7, coverage 4.

Then the question is: maximum, how many subsets of intervals can be chosen so that each interval can correspond to the limit <= 3? It is clear that for this case we simply delete the longest interval [1, 9], so the maximum number of subsets is 6 - 1 = 5.

? , ?

Answer 1

, . , #:

                //test
                int[][] grid =  { new int[]{ 1, 9 }, new int[] { 2, 8 }, new int[] { 2, 5 }, new int[] { 3, 4 }, new int[] { 6, 7 }, new int[] { 6, 8 } };
                SubsetFinder sf = new SubsetFinder(grid);
                int t1 = sf.GetNumberOfIntervals(1);//6
                int t2 = sf.GetNumberOfIntervals(2);//5
                int t3 = sf.GetNumberOfIntervals(3);//5
                int t4 = sf.GetNumberOfIntervals(4);//2
                int t5 = sf.GetNumberOfIntervals(5);//0


        class SubsetFinder
        {
            Dictionary<int, List<int>> dic;
            int intervalCount;
            public SubsetFinder(int[][] grid)
            {
                init(grid);
            }
            private void init(int[][] grid)
            {
                this.dic = new Dictionary<int, List<int>>();
                this.intervalCount = grid.Length;
                for (int r = 0; r < grid.Length; r++)
                {
                    int[] row = grid[r];
                    if (row.Length != 2) throw new Exception("not grid");
                    int start = row[0];
                    int end = row[1];
                    if (end < start) throw new Exception("bad interval");
                    for (int i = start; i <= end; i++)
                        if (!dic.ContainsKey(i))
                            dic.Add(i, new List<int>(new int[] { r }));
                        else
                            dic[i].Add(r);
                }
            }
            public int GetNumberOfIntervals(int coverageLimit)
            {
                HashSet<int> hsExclude = new HashSet<int>();
                foreach (int key in dic.Keys)
                {
                    List<int> lst = dic[key];
                    if (lst.Count < coverageLimit)
                        foreach (int i in lst)
                            hsExclude.Add(i);
                }
                return intervalCount - hsExclude.Count;
            }
        }

Answer 2

, , . :

, , , - , , , . :

, , , - . ( start, end), , , id .

, , , start end .

:

1,0, 2,0, 2,0, 2,0, 3,0, 4,1, 5,1, 6.0, 6.0, 7,1, 8,1, 8,1, 9,1

, , , , . ends . .

:

• start . end ( id) . , , ? , end, , , , . ( end , end)

• end , . end, , . end, , , , , .

, . , end , end , , , , , .

: N Log (N), N - , .