just now

admin 1.9k

Hyderabad

Question 1: The Crane Routing Problem

Problem Statement:

There are N cranes (numbered from 0 to N-1) arranged in a line along a road. Road begins at position 0. The K-th crane is located at distance P[K] from the beginning of the road and its arm length is equal to A[K]. The cranes cannot change their positions.

There is a package, initially located at position B, that has to be moved by the cranes to position E. The K-th crane can pick up the package only if the distance between its position and the package position is less than or equal to A[K] (the package is within arm range from the crane's position). A package can be moved by a crane to an arbitrary position within the crane's arm reach (between P[K] - A[K] and P[K] + A[K] for the K-th crane).

Example:

For example, if P[K] = 5 and A[K] = 3, the K-th crane can move packages anywhere between positions 2 and 8, including both of the boundaries.

Objective:

Determine whether it is possible to move the package from position B to position E using some (possibly all) of the cranes. Any crane can be used an arbitrary number of times.

Write a function to solve this logic.

just now

admin 1.9k

Hyderabad

Problem 1 Solution:

The Crane Routing Problem

Topics Involved / Prerequisites

• Interval Merging
• Sorting
• Connected Components (1D Geometry)

Overview

Every crane defines a specific range or "interval" on the road where it can pick up and drop off a package. Specifically, the K-th crane covers the interval [P[K] - A[K], P[K] + A[K]].

If the working ranges of two cranes overlap or touch, they can pass the package to each other. Therefore, a group of overlapping cranes forms a single, large contiguous "delivery zone." To determine if a package can be moved from point B to point E, we just need to verify if both B and E fall completely within one of these merged continuous zones.

Approach

1. Trivial Case: If the start position B is the same as the end position E, no movement is required, and we can immediately return true.
2. Generate Intervals: For each crane, calculate its exact coverage interval: [P[K] - A[K], P[K] + A[K]].
3. Sort the Intervals: Sort all crane intervals based on their starting positions in ascending order. This allows us to process them sequentially.
4. Merge Overlapping Intervals: Iterate through the sorted intervals. If the current interval overlaps with the previous one, merge them by extending the end boundary to the maximum reach. If it doesn't overlap, save the previous merged interval and start tracking a new one.
5. Check Coverage: Once all intervals are merged into disjoint zones, check if there is any single zone that covers both \min(B, E) and \max(B, E).

Time and Space Complexity

• Time Complexity: O(N log N) — Constructing the intervals takes O(N), but sorting them is the bottleneck and takes O(N log N). Merging and checking takes O(N).
• Space Complexity: O(N) — We need extra space to store the intervals and the merged zones.

Code Implementation (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canMovePackage(int b, int e, const vector<int>& p, const vector<int>& a) {
    // If the package is already at the destination
    if (b == e) return true;
    
    int n = p.size();
    if (n == 0) return false;

    // Step 1: Create coverage intervals for each crane
    vector<pair<int, int>> intervals;
    for (int i = 0; i < n; ++i) {
        intervals.push_back({p[i] - a[i], p[i] + a[i]});
    }
    
    // Step 2: Sort intervals based on starting positions
    sort(intervals.begin(), intervals.end());
    
    vector<pair<int, int>> mergedZones;
    int current_start = intervals[0].first;
    int current_end = intervals[0].second;
    
    // Step 3: Merge overlapping coverage zones
    for (int i = 1; i < n; ++i) {
        if (intervals[i].first <= current_end) {
            // Overlapping intervals: extend the reach if necessary
            current_end = max(current_end, intervals[i].second);
        } else {
            // No overlap: save the current zone and start a new one
            mergedZones.push_back({current_start, current_end});
            current_start = intervals[i].first;
            current_end = intervals[i].second;
        }
    }
    // Add the final zone
    mergedZones.push_back({current_start, current_end});
    
    // Step 4: Check if B and E are inside the same continuous zone
    int start_pos = min(b, e);
    int end_pos = max(b, e);
    
    for (const auto& zone : mergedZones) {
        if (zone.first <= start_pos && zone.second >= end_pos) {
            return true;
        }
    }
    
    return false;
}