You are given a list of records and an integer d representing the range of days from 1 to d.
Each record represents one blocked interval for one person.
Each record is given as a string in the format "id,start,end".
A record "id,start,end" means person id is not available on every day from start to end, inclusive.
Return all days between 1 and d on which every person is free. This list will be sorted in ascending order.
Follow-up: return all days on which the number of available people is greater than or equal to k.
For the purpose of this problem, the set of people is the set of distinct id values present in records.
Class
FreeDaysFinder
Methods
List<Integer> getDaysWhenEveryoneIsFree(List<String> records, int d)
- Returns all days from
1 to d on which every person is free.
- Each string in
records has format "id,start,end".
- A person is blocked on every day in the inclusive range
[start, end].
- A day is included only if all distinct people in
records are available on that day.
- The returned list must be in increasing order.
List<Integer> getDaysWhenAtLeastKPeopleAreFree(List<String> records, int d, int k)
- Returns all days from
1 to d on which at least k people are free.
- Each string in
records has format "id,start,end".
- A person is blocked on every day in the inclusive range
[start, end].
- The number of free people on a day is computed using the distinct people present in
records.
- The returned list must be in increasing order.
Constraints
1 ≤ d ≤ 100,0001 ≤ records.size() ≤ 100,0001 ≤ id ≤ 10,000,0001 ≤ start ≤ end ≤ d- Each record string is in the format
"id,start,end".
1 ≤ k ≤ number of distinct ids in records- Multiple records may exist for the same person.
Notes
- Day numbers are inclusive and start from
1.
- If a person has multiple records, that person is unavailable on the union of all blocked days from those records.
- If no day satisfies the condition, return an empty list.
Examples
Example 1
getDaysWhenEveryoneIsFree(records = List.of("1,2,3", "2,5,6"), d = 6)
Returns [1, 4]
Explanation:
Person 1 is blocked on days 2 and 3.
Person 2 is blocked on days 5 and 6.
So the days on which both people are free are 1 and 4.
Example 2
getDaysWhenAtLeastKPeopleAreFree(records = List.of("1,2,3", "2,5,6"), d = 6, k = 2)
Returns [1, 4]
Explanation:
There are 2 distinct people.
At least 2 people are free only on days 1 and 4.
Example 3
getDaysWhenAtLeastKPeopleAreFree(records = List.of("1,2,3", "2,5,6"), d = 6, k = 1)
Returns [1, 2, 3, 4, 5, 6]
Explanation:
On every day from 1 to 6, at least one person is free.
Example 4
getDaysWhenEveryoneIsFree(records = List.of("1,1,2", "1,5,5", "2,2,3", "3,4,4"), d = 5)
Returns []
Explanation:
The distinct people are 1, 2, and 3.
There is no day on which all three people are free at the same time.