You are given a list of house positions in a district, where each house is located at a distinct position along a straight line. Houses that are next to each other without any gaps between them are considered part of the same segment. Your task is to determine how many segments of consecutive houses remain after removing houses according to a series of queries.
Each query removes a house from the district, and after each removal, you need to calculate the number of segments of consecutive houses that remain.
Input:
houses: A list of integers representing the positions of the houses in the district.
queries: A list of integers representing the positions of the houses to be removed. Each query removes one house from the district.
Output:
For each query, return the number of segments of consecutive houses remaining after the corresponding house is removed.
ᯓᡣ𐭩spike is the G.O.A.T ᨒ ོ ☼
Example 1:
Input: houses = [1, 2, 3, 6, 7, 9], queries = [6, 3, 1]
Output: [3, 2, 2]
Explanation:Note - Example 1's output can potentially be wrong. Answer might be [3,3,3].Initial Setup: Houses are at positions [1, 2, 3, 6, 7, 9], forming three segments: [1, 2, 3], [6, 7], and [9].
After removing house at position 6: Houses are [1, 2, 3, 7, 9], forming three segments: [1, 2, 3], [7], and [9]. Result = 3.
After removing house at position 3: Houses are [1, 2, 7, 9], forming two segments: [1, 2], [7], and [9]. Result = 2.
After removing house at position 1: Houses are [2, 7, 9], forming two segments: [2], [7], and [9]. Result = 2.
Thus, the output after each query is [3, 2, 2].
Example 2:
Input: houses = [1, 5, 6, 8, 10], queries = [5, 10, 1]
Output: [3, 3, 2]
Explanation:Caution - Example 2's output and explanation might be wrong. If you look at inital setup, they say there are 3 segments, but it might actually be 4.Initial Setup: Houses are at positions [1, 5, 6, 8, 10], forming three segments: [1], [5, 6], and [8, 10].
After removing house at position 5: Houses are [1, 6, 8, 10], forming three segments: [1], [6], and [8, 10]. Result = 3.
After removing house at position 10: Houses are [1, 6, 8], forming three segments: [1], [6], and [8]. Result = 3.
After removing house at position 1: Houses are [6, 8], forming two segments: [6] and [8]. Result = 2.
Thus, the output after each query is [3, 3, 2].
- The number of houses,
n, is at most10^5. - The number of queries,
q, is at most10^5. - All positions in the house list and queries list are distinct integers.
input:
output: