Max Engagement Journey Score
At Clevertap, understanding user engagement patterns is crucial for product success. We often analyze sequences of user events to identify valuable 'journeys' that users take within our applications. This problem asks you to identify the most impactful user journey based on event scores and time proximity.
Implement the function maxEngagementJourneyScore that calculates the maximum total score achievable from a valid 'engagement journey'. A journey is considered valid if it meets the following criteria:
minEvents events.maxTimeGap.Your function should return the maximum possible total score for any such valid journey. If no valid journey can be formed, return 0.
events: An array of Event objects. Each Event object has two properties:
timestamp: number: The time (e.g., in milliseconds) when the event occurred.score: number: The engagement score associated with this event (can be positive, negative, or zero).maxTimeGap: number: A non-negative integer representing the maximum allowed time difference between consecutive events in a journey.minEvents: number: A positive integer representing the minimum number of events required for a journey to be considered valid.number representing the maximum total score of a valid engagement journey. Return 0 if no valid journey exists.events array is not guaranteed to be sorted by timestamp.maxTimeGap is 0, consecutive events must have identical timestamps. If minEvents is 1, any single event's score is a potential journey score.Examples
Example 1
Input:
events = [{timestamp: 1, score: 10}, {timestamp: 3, score: 5}, {timestamp: 5, score: 12}, {timestamp: 8, score: -3}, {timestamp: 10, score: 8}], maxTimeGap = 3, minEvents = 2
Output:
32
Note:
Sorted events: [{t:1,s:10}, {t:3,s:5}, {t:5,s:12}, {t:8,s:-3}, {t:10,s:8}]. One optimal journey is: {t:1,s:10} -> {t:3,s:5} -> {t:5,s:12} -> {t:8,s:-3} -> {t:10,s:8}. Total score = 10+5+12-3+8 = 32. All consecutive time gaps (2, 2, 3, 2) are <= 3, and event count (5) >= 2.
Example 2
Input:
events = [{timestamp: 1, score: 10}, {timestamp: 10, score: 5}, {timestamp: 20, score: 12}], maxTimeGap = 5, minEvents = 2
Output:
0
Note:
Sorted events are already in order. No two consecutive events have a time difference <= 5. For example, 10-1=9 > 5, and 20-10=10 > 5. Thus, no journey with at least 2 events can be formed. Returns 0.
Example 3
Input:
events = [{timestamp: 10, score: 50}, {timestamp: 1, score: 10}, {timestamp: 5, score: 20}], maxTimeGap = 10, minEvents = 1
Output:
80
Note:
Sorted events: [{t:1,s:10}, {t:5,s:20}, {t:10,s:50}]. All events are within maxTimeGap of 10 (5-1=4, 10-5=5). The journey {t:1,s:10} -> {t:5,s:20} -> {t:10,s:50} yields a total score of 10+20+50 = 80. Since minEvents is 1, even a single event's score would be considered if it were the maximum.
Constraints
1 <= events.length <= 20000 <= events[i].timestamp <= 10^9-1000 <= events[i].score <= 10000 <= maxTimeGap <= 10^91 <= minEvents <= events.lengthO(N^2) where N is events.length.O(N)timestamp_i < timestamp_{i+1} for selected events).minEvents and maxTimeGap values.Loading editor...