Maximum Square Area in Rectangle Intersection

When given coordinates for the bottom-left and top-right corners of multiple axis-aligned rectangles, the goal is to determine the area of the largest square that can fit entirely within the intersection of any two rectangles. The core logic involves identifying the overlapping region. If two rectangles overlap, the width of the overlap is defined by the difference between the minimum of the right edges and the maximum of the left edges. Similarly, the height is the difference between the minimum of the top edges and the maximum of the bottom edges.

If both the horizontal and vertical overlaps are positive, an intersection exists. The potential side length of a square in this intersection is the smaller of the overlap's width and height. However, this side length is further constrained by the dimensions of the original rectangles themselves; the square cannot be larger than the smaller side length of either of the two intersecting rectangles. The maximum area is the square of this limiting side length.

class Solution {
public:
    long long calculateMaxSquare(vector& bottomLeft, vector& topRight) {
        long long maxArea = 0;
        int size = bottomLeft.size();
        
        for (int i = 0; i < size; ++i) {
            for (int j = i + 1; j < size; ++j) {
                int x1 = bottomLeft[i][0], y1 = bottomLeft[i][1];
                int x2 = topRight[i][0], y2 = topRight[i][1];
                int x3 = bottomLeft[j][0], y3 = bottomLeft[j][1];
                int x4 = topRight[j][0], y4 = topRight[j][1];

                // Calculate overlap dimensions
                int overlapX = max(0, min(x2, x4) - max(x1, x3));
                int overlapY = max(0, min(y2, y4) - max(y1, y3));

                if (overlapX > 0 && overlapY > 0) {
                    long long sideCandidate = min((long long)overlapX, (long long)overlapY);
                    long long limitRect1 = min(x2 - x1, y2 - y1);
                    long long limitRect2 = min(x4 - x3, y4 - y3);
                    
                    long long maxSide = min({sideCandidate, limitRect1, limitRect2});
                    maxArea = max(maxArea, maxSide * maxSide);
                }
            }
        }
        return maxArea;
    }
};

Optimizing Index Marking Time

This problem requires finding the earliest second to mark all indices given a sequence of operations and time costs for each index. A greedy approach applied directly to the sequence often fails because marking an index too early or too late can block subsequent operations. However, the problem exhibits monotonicity: if it is possible to mark all indices by time T, it is also possible for any time greater than T. This property allows us to use binary search to find the minimum valid time.

To validate a specific candidate time `mid`, we work backwards. We traverse the sequence from the candidate time down to zero. For each index, we record the last occurrence within this timeframe. This greedy strategy assigns the marking moment as late as possible, maximizing the time available for decrementing the value in preceding steps. Once all specific moments are assigned, we simulate the process forward. We accumulate time for every step that is not a marking moment. When we reach a designated marking moment, we check if the accumulated time is sufficient to decrement the index's value to zero. If any step fails this check, the candidate time is invalid.

class Solution {
    bool isValid(vector<int>& nums, vector<int>& changeIndices, int timeLimit) {
        int n = nums.size();
        vector<int> markMoment(n, -1);

        // Greedy assignment: mark as late as possible
        for (int t = timeLimit; t >= 0; --t) {
            int idx = changeIndices[t] - 1;
            if (markMoment[idx] == -1) {
                markMoment[idx] = t;
            }
        }

        // Check if all indices have a valid marking time
        for (int t : markMoment) {
            if (t == -1) return false;
        }

        int timer = 0;
        for (int t = 0; t <= timeLimit; ++t) {
            int idx = changeIndices[t] - 1;
            if (markMoment[idx] == t) {
                // Perform marking operation
                if (timer < nums[idx]) return false;
                timer -= nums[idx];
            } else {
                // Accumulate time
                timer++;
            }
        }
        return true;
    }

public:
    int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) {
        int left = 0, right = changeIndices.size() - 1, result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(nums, changeIndices, mid)) {
                result = mid + 1; // Convert to 1-based index if required
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
};