Python icon indicating copy to clipboard operation
Python copied to clipboard
Published 2 weeks ago • verified publisher icon TheAlgorithms

feat: Added Weighted Interval Scheduling

Open BKarthik7 opened this issue 1 year ago • 5 comments

Describe your change:

This pull request introduces the implementation of the Weighted Interval Scheduling Algorithm in Python. A comprehensive explanation of the algorithm is available at https://en.wikipedia.org/wiki/Interval_scheduling#:~:text=their%20finishing%20times.-,Weighted,-%5Bedit%5D.

  • [x] Add an algorithm?
  • [x] Documentation change?

Checklist:

  • [x] I have read CONTRIBUTING.md.
  • [x] This pull request is all my own work -- I have not plagiarized.
  • [x] I know that pull requests will not be merged if they fail the automated tests.
  • [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
  • [x] All new Python files are placed inside an existing directory.
  • [x] All filenames are in all lowercase characters with no spaces or dashes.
  • [x] All functions and variable names follow Python naming conventions.
  • [x] All function parameters and return values are annotated with Python type hints.
  • [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.

BKarthik7 avatar Oct 04 '24 19:10 BKarthik7

@CodiumAI-Agent /describe --pr_description.extra_instructions=" For the title, use the format [type]: [summary] "

DerrickMcClain avatar Oct 04 '24 22:10 DerrickMcClain

@CodiumAI-Agent /improve --pr_code_suggestions.num_code_suggestions_per_chunk="4"

DerrickMcClain avatar Oct 04 '24 22:10 DerrickMcClain

Title

feat: Added Weighted Interval Scheduling

User description

Describe your change:

  • [x] Add an algorithm?
  • [x] Documentation change?

Checklist:

  • [x] I have read CONTRIBUTING.md.
  • [x] This pull request is all my own work -- I have not plagiarized.
  • [x] I know that pull requests will not be merged if they fail the automated tests.
  • [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
  • [x] All new Python files are placed inside an existing directory.
  • [x] All filenames are in all lowercase characters with no spaces or dashes.
  • [x] All functions and variable names follow Python naming conventions.
  • [x] All function parameters and return values are annotated with Python type hints.
  • [ ] All functions have doctests that pass the automated testing.
  • [x] All new algorithms include at least one URL that points to Wikipedia or another similar explanation.

PR Type

Enhancement, Documentation

Description

  • Implemented the Weighted Interval Scheduling algorithm to find the maximum weight subset of non-overlapping jobs.
  • Added latest_non_conflict and find_max_weight functions with detailed docstrings and doctests.
  • Updated DIRECTORY.md to include the new algorithm entry.

Changes walkthrough 📝

Relevant files
Enhancement
weighted_interval_scheduling.py
Implement Weighted Interval Scheduling Algorithm with Doctests

scheduling/weighted_interval_scheduling.py

  • Implemented the Weighted Interval Scheduling algorithm.
  • Added functions to find the latest non-conflicting job and calculate
    maximum weight.
  • Included doctests for the functions.
  • Provided a main block with example usage.
    		•  +74/-0   
    Documentation
    DIRECTORY.md
    Update DIRECTORY.md with Weighted Interval Scheduling       

    DIRECTORY.md

  • Added entry for Weighted Interval Scheduling in the scheduling
    section.
    		•  +1/-0     

    💡 PR-Agent usage: Comment /help "your question" on any pull request to receive relevant information

    QodoAI-Agent avatar Oct 04 '24 22:10 QodoAI-Agent

    PR Code Suggestions ✨

    Latest suggestions up to 129bba2

    CategorySuggestion                                                                                                                                    Score
    Possible bug
    Add a check for an empty input list to prevent index errors

    Consider adding a check to ensure that the input list jobs is not empty before
    proceeding with the algorithm in find_max_weight. This will prevent potential index
    errors when accessing jobs[0].

    scheduling/weighted_interval_scheduling.py [46-52]

    +if not jobs:
+    return 0
 jobs.sort(key=lambda ele: ele[1])
 length = len(jobs)
 dp = [0] * length
 dp[0] = jobs[0][2]  # The weight of the first job is the initial value
    Suggestion importance[1-10]: 9

    Why: This suggestion addresses a potential bug where accessing the first element of an empty list would cause an index error. Adding a check for an empty list is crucial for preventing runtime errors and ensuring the function behaves correctly with edge cases.

    		9
    Add error handling for job tuple structure to prevent unpacking errors

    Add error handling for the case where the job tuples do not contain exactly three
    elements, which could lead to unpacking errors.

    scheduling/weighted_interval_scheduling.py [47]

    +if any(len(job) != 3 for job in jobs):
+    raise ValueError("Each job must be a tuple of three elements (start_time, end_time, weight)")
 jobs.sort(key=lambda ele: ele[1])
    Suggestion importance[1-10]: 9

    Why: The suggestion adds necessary error handling to ensure that each job tuple contains exactly three elements, preventing potential unpacking errors. This is important for maintaining the robustness and reliability of the function.

    		9
    Performance
    Implement binary search in latest_non_conflict to improve efficiency

    Optimize the latest_non_conflict function by implementing a binary search instead of
    a linear search to find the latest non-conflicting job, improving the overall time
    complexity of the algorithm.

    scheduling/weighted_interval_scheduling.py [24-27]

    -for j in range(indx - 1, -1, -1):
-    if jobs[j][1] <= jobs[indx][0]:
-        return j
+low, high = 0, indx - 1
+while low <= high:
+    mid = (low + high) // 2
+    if jobs[mid][1] <= jobs[indx][0]:
+        if jobs[mid + 1][1] > jobs[indx][0]:
+            return mid
+        low = mid + 1
+    else:
+        high = mid - 1
 return -1
    Suggestion importance[1-10]: 8

    Why: The suggestion improves the performance of the latest_non_conflict function by replacing a linear search with a binary search, which is more efficient given the sorted nature of the jobs. This change enhances the overall time complexity of the algorithm.

    		8
    Maintainability
    Encapsulate job inclusion logic into a separate function for clarity

    Refactor the dynamic programming logic in find_max_weight to encapsulate the job
    inclusion logic into a separate function for better modularity and readability.

    scheduling/weighted_interval_scheduling.py [54-63]

    -include_weight = jobs[i][2]
-latest_job = latest_non_conflict(jobs, i)
-if latest_job != -1:
-    include_weight += dp[latest_job]
-dp[i] = max(include_weight, dp[i - 1])
+def calculate_inclusion_weight(i):
+    include_weight = jobs[i][2]
+    latest_job = latest_non_conflict(jobs, i)
+    if latest_job != -1:
+        include_weight += dp[latest_job]
+    return include_weight
+dp[i] = max(calculate_inclusion_weight(i), dp[i - 1])
    Suggestion importance[1-10]: 6

    Why: This suggestion improves code maintainability and readability by refactoring the job inclusion logic into a separate function. While it does not affect functionality, it enhances the modularity of the code.

    		6

    Previous suggestions

    Suggestions up to commit 129bba2
    CategorySuggestion                                                                                                                                    Score
    Performance
    Implement binary search in latest_non_conflict for efficiency

    Optimize the latest_non_conflict function by implementing a binary search instead of
    a linear search to improve the efficiency from O(n) to O(log n) per query.

    scheduling/weighted_interval_scheduling.py [24-27]

    -for j in range(indx - 1, -1, -1):
-    if jobs[j][1] <= jobs[indx][0]:
-        return j
+low, high = 0, indx - 1
+while low <= high:
+    mid = (low + high) // 2
+    if jobs[mid][1] <= jobs[indx][0]:
+        if jobs[mid + 1][1] > jobs[indx][0]:
+            return mid
+        low = mid + 1
+    else:
+        high = mid - 1
 return -1
    Suggestion importance[1-10]: 9

    Why: Implementing a binary search significantly improves the efficiency of the latest_non_conflict function from O(n) to O(log n), which is a substantial performance enhancement for large datasets.

    		9
    Possible bug
    Add a check for an empty job list to prevent errors

    Consider adding a check to ensure that the input list of jobs is not empty before
    sorting and processing in the find_max_weight function to prevent potential errors
    when accessing list elements.

    scheduling/weighted_interval_scheduling.py [47]

    +if not jobs:
+    return 0
 jobs.sort(key=lambda ele: ele[1])
    Suggestion importance[1-10]: 8

    Why: Adding a check for an empty job list before processing prevents potential errors when accessing list elements, ensuring robustness and preventing runtime exceptions.

    		8
    Add error handling for job tuple structure

    Add error handling for cases where the job tuples do not contain exactly three
    elements to prevent index errors during processing.

    scheduling/weighted_interval_scheduling.py [52]

    +if len(jobs[0]) != 3:
+    raise ValueError("Each job must be a tuple of (start_time, end_time, weight)")
 dp[0] = jobs[0][2]  # The weight of the first job is the initial value
    Suggestion importance[1-10]: 7

    Why: Adding error handling for job tuple structure ensures that each job is correctly formatted, preventing index errors and improving the robustness of the function.

    		7
    Maintainability
    Improve variable naming for clarity

    Use a more descriptive variable name than ele in the lambda function used for
    sorting jobs to enhance code readability.

    scheduling/weighted_interval_scheduling.py [47]

    -jobs.sort(key=lambda ele: ele[1])
+jobs.sort(key=lambda job: job[1])
    Suggestion importance[1-10]: 6

    Why: Using a more descriptive variable name like job instead of ele in the lambda function enhances code readability and maintainability, making the code more understandable.

    		6
    Suggestions up to commit 129bba2
    CategorySuggestion                                                                                                                                    Score
    Performance
    Implement binary search in latest_non_conflict to improve efficiency

    Optimize the latest_non_conflict function by implementing a binary search instead of
    a linear search to find the latest non-conflicting job, which will reduce the time
    complexity from O(n) to O(log n) per query.

    scheduling/weighted_interval_scheduling.py [24-27]

    -for j in range(indx - 1, -1, -1):
-    if jobs[j][1] <= jobs[indx][0]:
-        return j
+low, high = 0, indx - 1
+while low <= high:
+    mid = (low + high) // 2
+    if jobs[mid][1] <= jobs[indx][0]:
+        if mid == indx - 1 or jobs[mid + 1][1] > jobs[indx][0]:
+            return mid
+        low = mid + 1
+    else:
+        high = mid - 1
 return -1
    Suggestion importance[1-10]: 9

    Why: The suggestion to use binary search in latest_non_conflict significantly improves the function's efficiency by reducing the time complexity from O(n) to O(log n). This is a substantial performance enhancement, especially for large datasets.

    		9
    Enhancement
    Add a check for an empty job list to prevent errors and unnecessary computations

    Consider adding a check to ensure that the jobs list is not empty before proceeding
    with the sorting and DP table initialization in the find_max_weight function. This
    will prevent potential errors or unnecessary computations when the function is
    called with an empty list.

    scheduling/weighted_interval_scheduling.py [47]

    +if not jobs:
+    return 0
 jobs.sort(key=lambda ele: ele[1])
    Suggestion importance[1-10]: 8

    Why: This suggestion adds a check for an empty job list before proceeding with sorting and DP table initialization, which is a valuable enhancement to prevent errors and unnecessary computations. It ensures the function handles edge cases gracefully.

    		8
    Robustness
    Add error handling for malformed job entries to prevent runtime errors

    Add error handling for the case where the jobs list contains tuples that do not
    conform to the expected format (start_time, end_time, weight), to prevent runtime
    errors during sorting or weight calculations.

    scheduling/weighted_interval_scheduling.py [47]

    -jobs.sort(key=lambda ele: ele[1])
+try:
+    jobs.sort(key=lambda ele: ele[1])
+except IndexError:
+    raise ValueError("Each job must be a tuple of (start_time, end_time, weight)")
    Suggestion importance[1-10]: 7

    Why: Adding error handling for malformed job entries increases the robustness of the code by preventing runtime errors during sorting or weight calculations. This is a useful enhancement for ensuring input data integrity.

    		7
    Readability
    Use list comprehension for initializing the dp array to enhance code readability

    Replace the explicit loop for initializing the dp array with a list comprehension
    for improved readability and conciseness.

    scheduling/weighted_interval_scheduling.py [51-52]

    -dp = [0] * length
-dp[0] = jobs[0][2]
+dp = [jobs[0][2]] + [0] * (length - 1)
    Suggestion importance[1-10]: 5

    Why: This suggestion improves code readability by using a list comprehension for initializing the dp array. While it is a minor change, it enhances the code's conciseness and clarity.

    		5
    Suggestions up to commit 66d6969
    CategorySuggestion                                                                                                                                    Score
    Performance
    Implement binary search in latest_non_conflict for efficiency

    Optimize the latest_non_conflict function by implementing a binary search instead of
    a linear search to find the latest non-conflicting job, reducing the time complexity
    from O(n) to O(log n).

    scheduling/weighted_interval_scheduling.py [20-23]

    -for j in range(n - 1, -1, -1):
-    if jobs[j][1] <= jobs[n][0]:
-        return j
+low, high = 0, n - 1
+while low <= high:
+    mid = (low + high) // 2
+    if jobs[mid][1] <= jobs[n][0]:
+        if jobs[mid + 1][1] <= jobs[n][0]:
+            low = mid + 1
+        else:
+            return mid
+    else:
+        high = mid - 1
 return -1
    Suggestion importance[1-10]: 9

    Why: Replacing the linear search with a binary search in latest_non_conflict significantly improves performance from O(n) to O(log n), which is a substantial optimization for large datasets.

    		9
    Possible bug
    Add a check for an empty input list to prevent errors

    Consider adding a check to ensure that the input list jobs is not empty before
    proceeding with the algorithm in the find_max_weight function. This will prevent
    potential errors or unexpected behavior when an empty list is passed.

    scheduling/weighted_interval_scheduling.py [40-41]

    +if not jobs:
+    return 0
 jobs.sort(key=lambda x: x[1])
    Suggestion importance[1-10]: 8

    Why: Adding a check for an empty list in the find_max_weight function is crucial to prevent errors or unexpected behavior, especially since the function assumes a non-empty list. This enhances robustness and prevents potential runtime errors.

    		8
    Enhancement
    Add error handling for better feedback and debugging

    Add error handling or logging for the case when the find_max_weight function is
    called with an empty list of jobs, to provide feedback on why no processing was
    done.

    scheduling/weighted_interval_scheduling.py [66-68]

     if len(jobs) == 0:
-    print("No jobs available to process")
-    raise SystemExit(0)
+    logger.error("No jobs available to process")
+    raise ValueError("No jobs available to process")
    Suggestion importance[1-10]: 7

    Why: Enhancing error handling with logging provides better feedback and aids debugging, especially when the function is called with an empty list. This change improves the user experience by providing more informative error messages.

    		7
    Maintainability
    Improve variable naming for clarity and maintainability

    Use a more descriptive variable name than dp in the find_max_weight function to
    enhance code readability and maintainability.

    scheduling/weighted_interval_scheduling.py [45]

    -dp = [0] * n
+max_weight_up_to_job = [0] * n
    Suggestion importance[1-10]: 6

    Why: Using a more descriptive variable name than dp improves code readability and maintainability, making it clearer what the variable represents, which is beneficial for future code reviews and maintenance.

    		6

    QodoAI-Agent avatar Oct 04 '24 22:10 QodoAI-Agent

    @cclauss @tianyizheng02 can you please review my code

    BKarthik7 avatar Oct 07 '24 14:10 BKarthik7