Check if All Destinations in a Route are Covered - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To check if every destination in the route [start_dest, end_dest] is covered by at least one trip.
  • What input is provided?
    • A 2D array trips and two integers start_dest and end_dest.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Create a set of all destinations in the route, then remove destinations covered by the trips. If the set is empty, all destinations are covered.

1) Create a set `needed` of all destinations from `start_dest` to `end_dest`.
2) Iterate through the `trips` array:
   - For each trip, remove the covered destinations from `needed`.
3) If `needed` is empty, return `True`; otherwise, return `False`.

⚠️ Common Mistakes

• Not correctly handling overlapping trips.

I-mplement

def is_route_covered(trips, start_dest, end_dest):
    # Create a set of all destinations from start_dest to end_dest
    needed = set(range(start_dest, end_dest + 1))

    # Remove covered destinations from the set
    for start, end in trips:
        for dest in range(start, end + 1):
            if dest in needed:
                needed.remove(dest)

    # If the set is empty, all destinations were covered
    return len(needed) == 0