Simpler solution to Points Covering Intervals

#1

(Points Covering Intervals: prob # 13.12 in ver 1.2.1)

prior to posting, i checked my solution against the latest solution on the website against 999 randomly generated tests each run multiple times.

my solution gets rid of extra collections like covering_list, covered_set, sorts only half the items (sorting n vs 2n items… because i only sort the right endpoints…), and i think shorter/simpler, so maybe easier to understand?)

existing given solution in the website (only the parts that’s relevant):

  public static class EndPoint implements Comparable<EndPoint> {
      public Interval ptr;
      public boolean isLeft;

      public EndPoint(Interval i, boolean il) {
         ptr = i;
         isLeft = il;
      }

      public int compareTo(EndPoint that) {
         int a = isLeft ? ptr.left : ptr.right, b = that.isLeft ? that.ptr.left : that.ptr.right;
         if (a != b) {
            return a - b;
         }
         // Give preference to left endpoint.
         if (isLeft && !that.isLeft) {
            return -1;
         } else if (!isLeft && that.isLeft) {
            return 1;
         } else {
            return 0;
         }
      }
   }

   public static List<Integer> findMinimumVisits(Interval[] intervals) {
      List<EndPoint> endpoints = new ArrayList<>();
      for (Interval aI : intervals) {
         endpoints.add(new EndPoint(aI, true));
         endpoints.add(new EndPoint(aI, false));
      }

      Collections.sort(endpoints);
      return findMinimumVisitsHelper(endpoints);
   }

   private static List<Integer> findMinimumVisitsHelper(List<EndPoint> endpoints) {
      List<Integer> S = new ArrayList<>(); // A minimum set of visit times.
      Set<Interval> covered = new HashSet<>();
      List<Interval> covering = new ArrayList<>();
      for (EndPoint e : endpoints) {
         if (e.isLeft) {
            covering.add(e.ptr);
         } else if (!covered.contains(e.ptr)) {
            // e's interval has not been covered.
            S.add(e.ptr.right);
            // Adds all intervals in covering to covered.
            covered.addAll(covering);
            covering.clear(); // e is contained in all intervals in
                              // covering.
         }
      }
      return S;
   }

my solution:

public static List<Integer> minVisitsAlt(Interval[] intervals) {
	Arrays.sort(intervals, new Comparator<Interval>() {
		public int compare(Interval o1, Interval o2) {
			return o1.right - o2.right;
		}
	});
	
	List<Integer> ret = new ArrayList<Integer>();
	Integer lastVisit = 0;

	for (Interval interval : intervals) {
		if (!ret.isEmpty() && lastVisit >= interval.left) {
			continue;
		}

		lastVisit = interval.right;
		ret.add(lastVisit);
	}

	return ret;
}

so basically, the key difference between two algorithms is the use of lastVisit_integer vs covered_set & covered_list for checking whether a given interval is already covered by previous visits; this also gets rid of needing to sort the left endpoint.

given the task sorted by their right endpoints, only thing we need to check whether the given task is already covered by previous visits is to check the given task’s left endpoint against the most recent lastVisit integer;

we know that any interval whose left endpoint is <= than the lastVisit value is already covered.
if above is not true, then that means there is an interval whose left endpoint <= lastVisit && right endpoint >= lastVisit but not covered… which is contradictory so can’t be true.

if left endpoint is bigger than the lastVisit, then the given interval is not covered, and among the uncovered intervals, this one has the earliest right endpoint, so we have to visit that right endpoint so add that.

then loop.

so lastVisit is the only value we need to keep; no need for covering_list or covered_set. thereby making the solution simpler; (and less memory due to no need of extra covered_set and covering_list)

0 Likes
An alternative solution to the interval covering problem (18.4 in v1.5.1)
#2

I think it’s comparable to the solution i proposed there Alternative to 14.8?
Our explanations are slightly different, but if you can make sense of what i proposed maybe you can infer the correctness of your solution
( i cant understand java anymore :wink: )

0 Likes
#3

@zebullon

i just read your solution, and your solution can be simplified in your bool Intersect() step.

your current intersect step (in java):

 static boolean Intersect(Interval a, Interval b) {
      if (Math.min(a.right, b.right) < Math.max(a.left, b.left)) {
         return false;
      }
      
      a.left = Math.max(a.left, b.left);
      a.right = Math.min(a.right, b.right);
      return true;
   }

to…

   static boolean Intersect(Interval a, Interval b) {
      if (a.right < b.left) {
         return false;
      }
      
      a.right = Math.min(a.right, b.right);
      return true;
   }

… because Math.max(a.left, b.left) always == b.left (due to your sorting)…

then since we only need to compare against b.left in the next loop, we don’t need to be keep updating a.left so remove that. (this also requires us to set the visit time based on a.right instead of a.left after end of intersects since we’re not updating a.left – you’ve already mentioned your solution works either way - and i verified that to be true)

but now, if you had sorted by your right endpoints instead of left (like i’m doing), then you can further simplify Intersect func to…

   static boolean Intersect(Interval a, Interval b) {
      return a.right >= b.left;
   }

and this is possible because if you had sorted by your right endpoints, then Math.min(a.right, b.right) is always == a.right, so you don’t need to be keep updating a.right to a new value.
a.left can be ignored in comparison check because it’s always <= a.right by definition of intervals; so if b.left > a.left, then it’s covered by above code; if a.left >= b.left, then above equality will return true anyway.

then after simplifying to this much, your solution pretty much becomes like mine.

rest of your solution modified in java:

   public static List<Integer> minVisitsAlt2(Interval[] intervals) {
      List<Integer> result = new ArrayList<Integer>();
      Arrays.sort(intervals, new Comparator<Interval>(){
         public int compare(Interval o1, Interval o2) {
            return o1.right - o2.right; // this is modified to sort by right.
         }
      });
      
      int i = 0;
      while (i != intervals.length) {
         Interval in = intervals[i];
         while (i != intervals.length && Intersect(in, intervals[i])) {
            ++i;
         }
         result.add(in.right); // modified to do it on in.right
      }
      return result;
   }

so yeah, my solution is further simplification to your solution. verified this modification of your solution by running it against that 999 tests multiple times.

0 Likes
#4

Thanks for the thorough explanation on the point of divergence in our solution :wink:

0 Likes